基础篇

• BSGS(baby-step giant-step)，即大步小步算法。常用于求解离散对数问题。形象化的说，该算法可以在\(O(\sqrt p)\)的时间内求解\(a^x \equiv b(\mod p)\)
• 其中\(a \perp b\)。方程的解\(x\)满足\(0\le x < p\)。(不要求\(p\)为素数)
• 算法描述
• 令\(x=A\lceil {\sqrt p} \rceil-B\)其中\(0 \le {A,B} \le {\lceil {\sqrt p} \rceil}\)，则有\(a^{A\lceil{\sqrt p} \rceil-B}\equiv b(\mod p)\)，变换，则有\(a^{A\lceil {\sqrt p} \rceil}\equiv b(\mod p)\)
  我们已知\(a,b\)，所以我们可以先算出等式右边的\(ba^B\)的所有取值，枚举B用hash/map存下来，然后逐一计算\(a^{A\lceil {\sqrt p}\rceil}\)，枚举\(A\)寻找是否有与之相等的\(ba^B\)，从而我们可以得到所有的\(x\),\(x=A\lceil {\sqrt p}\rceil-B\)
  注意到\(A\),\(B\)均小于\(\sqrt p\)，所以时间复杂度为\(O(\sqrt p)\)，用``map```则多一个log

进阶篇

求解

BSGS