BSGS算法
BSGS算法是一种用于解决离散对数问题的算法,它的全称是Baby Step Giant Step,意为小步大步。然而我并不知到为什么要叫这个名字
离散对数问题
假设有一个同余方程$a^x \equiv b \pmod m$,其中$a,b,m$都是给定的整数,$a$与$m$互素。如何求解$x$的值?
第一个想法可能是暴力枚举,将$x$从$0$开始枚举到$m-1$,直到找到一个满足方程的$x$。时间复杂度是$O(m)$,如果$m$很大就挂了。
BSGS算法
既然暴力不行,那么我们就要想办法降低时间复杂度。BSGS算法就是一种优化的算法,它的时间复杂度是$O(\sqrt{m})$。它的思想也很简单。
首先我们令$x=A\sqrt{m}-B$,其中$A,B$是两个整数且$0\leq A,B\leq \sqrt{m}$。那么原方程就变成了$a^{A\sqrt{m}-B} \equiv b \pmod m$,即$a^{A\sqrt{m}} \equiv b\cdot a^B \pmod m$。
我们可以将方程分解为两个方程:
对于第一个方程,我们可以从$1$到$\sqrt{m}$枚举$B$的值,用一个$map$存对应$B$的值。对于第二个方程,依旧从$0$到$\sqrt{m}$枚举$A$的值,然后在$map$中查找是否有相等的$b\cdot a^B$,获取$B$的值,最后得到$x$的值。
1 | //a^x=b(mod p) |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Fogflea's blog!
评论