BSGS

BSGS算法（baby step giant step，大步小步算法），又叫北上广深算法（不是），是一种基于中间相遇思想求解离散对数的算法，即求解类似于ax≡b(modm)a^x\equiv b\pmod max≡b(modm)的方程。 BSGS算法 首先介绍最普通的BSGS算法。普通的BSGS算法要求mmm和aaa要互质，既然互质，那么根据欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1\pmod m aφ(m)≡1(modm) 也就是说，ax(modm)a^x \pmod max(modm)以φ(m)\varphi(m)φ(m)为周期循环，那么如果方程有解，解一定在000到φ(m)\varphi(m)φ(m)之间，如果暴力枚举，当mmm为质数时φ(m)\varphi(m)φ(m)最大为m−1m-1m−1，最坏复杂度为O(m)O(m)O(m)。 普通的BSGS算法就是对上述暴力算法的一个优化，我们可以把xxx改成At−BAt - BAt−B，那么原式变成aAt−B≡b(modm)a^{At - B} \equiv b \pmod maAt−B≡b(m ...