学习笔记 - BSGS大步小步算法

北上广深 拔山盖世……
还是叫大步小步吧……


· 算法概述

BSGS算法 又叫 大步小步算法。用于求解关于 $x$ 的方程 $A^x\equiv B\pmod{P}$ ($A$,$B$,$P$ 为已知),其中 $P$ 是质数 。

当然方程有可能无解。


· 算法证明

  1. 首先证明“如果原方程有解,则在 $x\in[0,P-1)$ 范围内有解”:

    根据费马小定理:$A^{P-1}\equiv 1\pmod{P}$ ;

    那么可以得到:$A^{x+k(P-1)}\equiv A^x\pmod{P}$ ($k$ 为整数);

    即 $A^x\equiv A^{x\bmod (P-1)}\pmod P$ ;得证。

  2. 令 $x=pm-q$ ($m$ 为一个常数且 $q<m$),那么原方程就变为 $A^{pm-q}\equiv B\pmod{P}$ ;

  3. 两边同乘 $A^q$ :$A^{pm}\equiv BA^q\pmod{P}$ ;

  4. 先枚举 $q\in[0,m)$ 并算出对应的 $(A^q \bmod P)$ 存入集合;

    再枚举 $p$ 直到 $pm+q>P-1$ ,计算 $(A^{pm}\bmod P)$ 并在集合里查找,如果找到了,就找到了一个解;

时间复杂度 $O(\max(m,\lceil\frac{P}{m}\rceil))$ 。

所以当 $m=\lceil\sqrt{P}\rceil$ 时,BSGS的时间复杂度达到最小 $O(\sqrt P)$ 。


· 例题(Discrete Logging ##POJ-2417##

多组数据,每次给出 $A,B,P$ ,求关于 $x$ 的方程的 $A^x\equiv B\pmod{P}$ 的最小非负整数解。如果无解输出 no solution

Tab. $P< 2^{31},2\leq A<P,1\leq B<P$

- 解析

用 map 会 TLE,手打链表 hash 。

然后特判一下 $B=1$ 的时候直接 $x=0$ 。

- 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const ll MOD=1389001;
ll B,N,P; //B^x=N (mod P)
ll adj[MOD],lst[2*MOD][2],nxt[2*MOD],cnt;
ll QPow(ll a,ll b){
ll res=1;
while(b){
if(b&1ll) res=res*a%P;
a=a*a%P;
b>>=1ll;
}
return res%P;
}
int SearchHash(ll num){
ll fnum=num%MOD;
for(int i=adj[fnum];i!=-1;i=nxt[i])
if(lst[i][0]==num)
return i;
return -1;
}
void Insert(ll num,ll val){
ll fnum=num%MOD;
lst[++cnt][0]=num;
lst[cnt][1]=val;
nxt[cnt]=adj[fnum];
adj[fnum]=cnt;
}
int main(){
while(~scanf("%lld%lld%lld",&P,&B,&N)){
if(N==1){printf("%d\n",0);continue;}
memset(adj,-1,sizeof adj);cnt=0;
ll M=(ll)ceil(sqrt(P));//x=pM-q
//B^(pM)=NB^q (mod P)
for(ll q=0,num=N;q<M;q++){
int X=SearchHash(num);
if(X==-1) Insert(num,q);
else lst[X][1]=q;
num=num*B%P;
}
ll BM=QPow(B,M);
bool abl=false;
for(ll p=1,num=1;p<=M;p++){
num=num*BM%P;
int X=SearchHash(num);
if(X!=-1){
abl=true;
printf("%lld\n",p*M-lst[X][1]);
break;
}
}
if(!abl) printf("no solution\n");
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%