Baby-Step Giant-Step

BSGS 算法将离散对数 x=im+j（m=ceil(√n)）分两步：预计算 g^j（baby）再搜索 h*(g^(-m))^i（giant）。

用途

时间-空间折中的离散对数求解，复杂度 O(√n)。

令 m=ceil(√n)。Baby step：计算并存储 {g^j : 0≤j<m}。Giant step：对 i=0,1,... 计算 h*g^(-im)，查表匹配则 x=im+j。时间 O(√n)，空间 O(√n)。