学习笔记 - 扩展BSGS

学习了BSGS再学扩展的……


· 算法简述

- 前置算法

  • BSGS
  • GCD

- 大致内容

解决关于 $x$ 的方程 $A^x\equiv B\pmod{P}$ ,但是与 BSGS 不同的是 $A$ 和 $P$ 不需要互质(似乎“扩展”就是去掉了互质的条件)


· 算法证明

  1. 根据原方程,我们把它写成 $CA^x+kP=B​$ ($k​$ 是整数,最开始 $C=1​$);
  2. 因为 $A,P​$ 不互质,令 $g=(A,P)​$ ;
  3. 将 1. 中的方程两边同除 $g$ ,得 $\frac{AC}{g}A^{x-1}+k\frac Pg=\frac Bg$;
  4. 但是上式左边是整数,如果右边是 分数 就无解了;
  5. 再把 3. 的等式还原成同余方程式:$\frac {AC}gA^{x-1}\equiv \frac Bg\pmod{\frac Pg}$ ;
  6. 上式中的 $\frac {AC}g$ 看做一个系数 $C’$,令 $x’=x-1$ ,$B’=\frac Bg$,$P’=\frac Pg$ ,则上式变为 $C’A^{x’}\equiv B’\pmod {P’}$ ;
  7. 因为 $C’$ 与 $P’$ 必然互质,那么 $C’A^{x’}$ 与 $P’$ 是否互质决定于 $A$ 和 $P’$ ;
  8. 所以重复上述过程,直到 $A$ 与 $P’$ 互质为止;
  9. 计 8. 的重复次数为 $t$;
  10. 这时候就可以用 BSGS 完成了,解出来的值为 $x-t$ ;

· 算法实现

(估计看上面的证明一些reader会懵,把 C++ 的实现写一下)

- 前置函数

  1. int BSGS(int A,int B,int P,int pro) 是改变后的BSGS求解 $pro*A^x\equiv B\pmod P$ ($A,P$ 互质)的解;
  2. int QPow(int A,int B,int mod) 是快速幂求解 $A^B\bmod P​$;
  3. int GCD(int A,int B) 是最大公约数求解 $(A,B)$;

- 扩展BSGS函数 (exBSGS)

  1. 参数 int exBSGS(int A,int B,int P),定义同 BSGS(A,B,P,pro) ,只是 $A,P$ 可以不互质;
  2. 定义 int tot 表示 3. 循环的次数,int pro 表示 $C’A^{x-t}$ 前面的系数 $C’$;
  3. 循环:
    • 判断 GCD(A,P)==1 ,是则退出循环;
    • 否则记 int g=GCD(A,P)
    • 如果 B%g!=0 ,则无解
    • P/=g , B/=g , tot++pro*=A/g
  4. 此时我们就要求解 $pro*A^{x-tot}\equiv B\pmod{P}$ ;
  5. 用 BSGS 得到 $x-tot$ 的值,则 x=BSGS(A,B,P,pro)+tot

· 源代码(##POJ-3243##

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int MOD=1000037;
struct HASH{
struct NODE{
ll key,val;
int nxt;
NODE(){}
NODE(ll _key,ll _val,int _nxt):key(_key),val(_val),nxt(_nxt){}
}nod[(int)2e6];
int adj[MOD],cnt;
void Rebuild(){memset(adj,-1,sizeof adj);cnt=0;}
int Search(ll key){
int tag=key%MOD;
for(int i=adj[tag];i!=-1;i=nod[i].nxt)
if(nod[i].key==key)
return i;
return -1;
}
void Insert(ll key,ll val){
int tag=key%MOD;
nod[++cnt]=NODE(key,val,adj[tag]);
adj[tag]=cnt;
}
}has;
ll GCD(ll A,ll B){return B? GCD(B,A%B):A;}
ll QPow(ll A,ll B,ll mod){
ll res=1ll;
while(B){
if(B&1ll) res=res*A%mod;
A=A*A%mod;
B>>=1;
}
return res%mod;
}
ll BSGS(ll A,ll B,ll P,ll pro=1ll){
ll w=(ll)ceil(sqrt(P));
for(ll j=0,num=B;j<=w;j++){
int res=has.Search(num);
if(res==-1) has.Insert(num,j);
else has.nod[res].val=j;
num=num*A%P;
}
ll fnum=QPow(A,w,P);
for(ll i=1,num=pro;i<=w;i++){
num=num*fnum%P;
int res=has.Search(num);
if(res!=-1)
return i*w-has.nod[res].val;
}
return -1;
}
ll exBSGS(ll A,ll B,ll P){
ll tot=0,pro=1;
while(true){
ll g=GCD(A,P);
if(g==1) break;
if(B%g) return -1ll;
tot++;B/=g;P/=g;
pro=pro*(A/g)%P;
}
B=B*QPow(A,tot,P)%P;
return BSGS(A,B,P,pro);
}
int main(){
ll A,B,P; //A^x=B (mod P)
while(~scanf("%lld%lld%lld",&A,&P,&B) && A && B && P){
B%=P;has.Rebuild();
ll res=exBSGS(A,B,P);
if(res==-1) printf("No Solution\n");
else printf("%lld\n",res);
}
return 0;
}

The End

Thanks for reading!

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

0%