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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//a^x=b(mod p)
LLI BSGS(int a,int b,int p){
if(a%p==0||b%p==0){//特殊情况
if(b%p==0&&a%p==0)return 1;
else return -1;
}

map<LLI,LLI> mp;
LLI cur=1,t=sqrt(p)+1;
for(LLI B=1;B<=t;++B){
cur=cur*a%p;
mp[b*cur%p]=B;
}
LLI now=cur;
for(LLI A=1;A<=t;++A){
if(mp[now])return A*t-mp[now];
now=now*cur%p;
}return -1;
}