基础篇
- 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
原文：https://www.cnblogs.com/wuchen-place/p/15011968.html
