BSGS&exBSGS

发表于 更新于 分类于

BSGS (Baby Steps Giant Steps)从入门到入土

BSGS (Baby Steps Giant Steps)从入门到入土

1.BSGS

求解如关于$x$的方程$A^x≡B \mod p$ 的最小整数解。$(A,p互质,p为质数)$

不难发现$x<=p$ 因为会出现循环。

靠虑将$x$分解为$i\times sqrt(x)-j$ 。

则原式化为$A^{i\times \lceil sqrt(x)\rceil}\times A^{-j}≡B \mod p$

对$A^{-j}$求逆元得$A^{i\times \lceil sqrt(x)\rceil}≡B\times A^j \mod p$

因为可以求一个同余方程$A^{-j}\times inv_{A^{-j}}≡1 mod p$

显而易见$inv_{A^{-j}}$即为$A^j$ ,其实有点像移项，可惜$p$不与$A$互质移不过来，可能导致左边$mod p$后为$0$

然后可知在$mod p$的意义下左右两式相等。

所以就可以用$map$吧左右的值映射成它的指数，先做右边($j$从$0$枚举到$\lceil sqrt(x)\rceil$),并把每次的$j$映射到$map$以$B\times A^j$为下标的空间中。然后做左边($i$从$1$枚举到$ \lceil sqrt(x)\rceil$)，每次查表搞一搞，第一次遇到相同的值就可以拿现在的$i\times \lceil sqrt(x)\rceil$与表中的$j$相减即为最小值，因为此时$i\times \lceil sqrt(x)\rceil$最小，$j$最大。

理论时间复杂度为$O(sqrt(p))$,但由于用了$map$所以多了红黑树查值的复杂度，所以多了个$log$。

代码

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
#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
	long long f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
long long KSM(long long base,long long index,long long p)
{
	long long Res=1;
	while (index)
	{
		if (index%2==1) Res*=base,Res%=p;
		base*=base;
		base%=p;
		index/=2;	
	} 
	return Res%p;
}
long long BSGS(long long a,long long b,long long p)
{
	map <long long,long long> m;
	long long X=(long long)ceil(sqrt(p));
	m[b]=0;
	long long Ans_=b;
	for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
	long long Ans__=KSM(a,X,p);
	long long Ans___=1,Ans=-1;
	for (int i=1;i<=X;i++) 
	{
		Ans___*=Ans__,Ans___%=p;
		if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
	}
	return Ans;
}
int main() 
{
	Read(p),Read(a),Read(b);
	long long answer=BSGS(a,b,p);
	if (answer==-1) cout<<"no solution"<<endl;
	else cout<<answer<<endl;
	return 0;
}

2.exBSGS

若$A,p$不互质，那普通的$BSGS$就难以胜任了，所以需要使用$exBSGS$

其实也很简单，假设$t=gcd(A,p)$,则可推出$A^{x-1}\times \frac{A}{t}≡\frac{B}{t} \mod p$

若$t\nmid B$,则只有$B=1$时有$x=0$的最小解

若$t \mid b $,则当$t=1$时用$BSGS$,求解即可。

反复执行，直至$A,p$互质。

最后，若此过程需要反复进行$k$次,则答案为$BSGS$的解$x+k$。

代码

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
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
long long b,p,a;
void Read(long long &x)
{
	long long f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
long long gcd(long long a,long long b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}
long long KSM(long long base,long long index,long long p)
{
	long long Res=1;
	while (index)
	{
		if (index%2==1) Res*=base,Res%=p;
		base*=base;
		base%=p;
		index/=2;	
	} 
	return Res%p;
}
void ex_gcd(long long a,long long b,long long &d,long long &x,long long &y) {
	if (b==0) x=1,y=0,d=a;
	else	
	{
		ex_gcd(b,a%b,d,x,y);
		long long tmp=x;x=y;y=tmp-a/b*y;
	}
}
long long inv(long long a,long long b)
{
    long long x,y,d;
    ex_gcd(a,b,d,x,y);
    return (x%b+b)%b;
}
long long BSGS(long long a,long long b,long long p)
{
	map <long long,long long> m;
	long long X=(long long)ceil(sqrt(p));
	m[b]=0;
	long long Ans_=b;
	for (int i=1;i<=X;i++) Ans_*=a,Ans_%=p,m[Ans_]=i;
	long long Ans__=KSM(a,X,p);
	long long Ans___=1,Ans=-1;
	for (int i=1;i<=X;i++) 
	{
		Ans___*=Ans__,Ans___%=p;
		if (m.count(Ans___)) {Ans=i*X-m[Ans___];break;}
	}
	return Ans;
}
long long exBSGS(long long a,long long b,long long p)
{
    if (b==1||p==1)return 0;     
    long long g=gcd(a,p),k=0,na=1;
    while (g!=1)
    {
        if (b%g!=0)return -1;   
        k++;b/=g;p/=g;na=na*(a/g)%p;
        if (na==b)return k;   
        g=gcd(a,p); 
    }
    long long f=BSGS(a%p,b*inv(na,p)%p,p);
    if (f==-1)return -1;
    return f+k;
}

int main() 
{
	while (1)
	{
	Read(a),Read(p),Read(b);
	if (p==0||a==0||b==0) break;
	long long answer=exBSGS(a,b,p);
	if (answer==-1) cout<<"No Solution"<<endl;
	else cout<<answer<<endl;
	}
	return 0;
}