学习笔记 - 扩展BSGS | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 扩展BSGS

发表于 更新于 分类于 Valine：

学习了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 ，欢迎提问~