[BSGS]大步小步算法

问题

BSGS被用于求解离散对数，即同余方程：

[A^xequiv Bpmod{P} ]

求(x)的最小非负整数解。

保证(Aperp P)(互质)。

分析

首先，我们根据费马小定理，有

[A^{P-1}equiv 1pmod{P} ]

则显然有

[A^{x-k(P-1)}equiv A^xpmod{P} ]

即

[A^{xmod{P-1}}equiv A^xpmod{P} ]

那么显然(x<P-1)，我们就得到了一个(O(P))的算法，然而太慢了。

考虑分块算法，对(x)每(m)分一块，则有

[A^{im-j}equiv Bpmod{P} ]

移项整理

[left(A^m ight)^iequiv A^j Bpmod{P} ]

那么我们枚举(i)，就可以求出(A^j)。再对于(jin[0,m-1])的(A^j)存进哈希表/map，就可以得到(x=im-j)了。如果不考虑查询哈希表/map的时间，则时间复杂度为(O(m+frac{P}{m}))。

那(m)应该取何值呢？由基本不等式显然有：

[m+frac{P}{m}gesqrt{mfrac{P}{m}}=sqrt{P} ]

当(m=frac{P}{m})时取等。

那么我们令(m=lceilsqrt{P} ceil)，就得到了一个(O(sqrt{P}))的算法。

代码

(-1)为无解。

ll BSGS(ll a,ll b,ll p){
	if(!a)return b?-1:1;
	if(b==1)return 0;
	map<ll,ll>mp;
	ll m=ceil(sqrt(p)),ax=1;
	for(int i=0;i<m;i++){
		mp[ax]=i;
		ax=ax*a%p;
	}
	ll am=pow(a,m,p),aj=am*pow(b,p-2,p)%p;
	for(int i=1;i<=m;i++){
		if(mp.count(aj))return m*i-mp[aj];
		aj=aj*am%p;
	}
	return -1;
}

例题

[BZOJ2242][SDOI2011]计算器

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
int t,k;
ll y,z,p;
ll pow(ll a,ll b,ll p){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
ll BSGS(ll a,ll b,ll p){
    if(!a)return b?-1:1;
    if(b==1)return 0;
    map<ll,ll>mp;
    ll m=ceil(sqrt(p)),ax=1;
    for(int i=0;i<m;i++){
        mp[ax]=i;
        ax=ax*a%p;
    }
    ll am=pow(a,m,p),aj=am*pow(b,p-2,p)%p;
    for(int i=1;i<=m;i++){
        if(mp.count(aj))return m*i-mp[aj];
        aj=aj*am%p;
    }
    return -1;
}
int main(){
	scanf("%d%d",&t,&k);
	while(t--){
		scanf("%lld%lld%lld",&y,&z,&p);
		if(k==1)printf("%lld
",pow(y,z,p));
		else if(k==2){
			if(y%p==0)printf("Orz, I cannot find x!
");
			else printf("%lld
",pow(y,p-2,p)*z%p);
		}else{
			ll ans=BSGS(y%p,z%p,p);
			if(~ans)printf("%lld
",ans);
			else printf("Orz, I cannot find x!
");
		}
	}
}