【算法】BSGS算法

BSGS算法

BSGS算法用于求解关于x的模方程\(A^x\equiv B\mod P\)（P为质数），相当于求模意义下的对数。

思想：

由费马小定理，\(A^{p-1}\equiv 1\mod P\)，在p-1次方后开始循环，所以若原方程有解，\(x_{min}\in[0,P-1]\)。

设\(x=i*m+j\)，有\(A^{i*m+j}\equiv B\mod P\)，移项得\({(A^m)}^i\equiv B*A^{-j}\mod P\)，类似天天爱跑步，对于左右互不影响的等式可以开桶统计。例如可以枚举i，检查另一侧是否有对应的j满足条件。

实现时，先把一侧的值存入map或hash表，再在另一侧枚举。写成\(x=i*m-j\)的形式，可以避免求逆元。

时间复杂度：\(j\in[0,m-1]\)，\(i\in [0,\frac p m]\)，复杂度为\(O(\max(m,\frac p m))\)，当\(m=\sqrt p\)时取最优，为\(O(\sqrt p)\)。

细节：

特判A==0的情况。
写成\(x=i*m-j\)，j从0枚举到m，i从1枚举到m，因为\(0=1*m-m\)。
枚举j时，如果模出结果相同，在hash表中用大的j覆盖小的j，因为\(x=i*m-j\)，显然j越大x越小。
传入时A、B先模P。

Code(POJ2417 Discrete Logging)：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Mod=20180801,N=3e7+5;

struct Hashtable{

	int size,key[N],nxt[N],head[N];

	ll val[N];

	inline void clear(){

		memset(head,0,sizeof(head));

		size=0;

	}

	inline int hash(ll Key){

		return Key%Mod;

	}

	inline ll find(ll Key){

		for(int i=head[hash(Key)];i;i=nxt[i]) if(key[i]==Key) return val[i];

		return -1;

	}

	inline void insert(ll Key,ll Val){

		for(int i=head[hash(Key)];i;i=nxt[i]) if(key[i]==Key) return (void) (val[i]=Val);

		key[++size]=Key;val[size]=Val;nxt[size]=head[hash(Key)];head[hash(Key)]=size;

	}

}mp;

ll qpow(ll a,ll b,ll p){

	ll res=1;

	for(;b;b>>=1,a=a*a%p) if(b&1) res=res*a%p;

	return res%p;

}

ll BSGS(ll a,ll b,ll p){

	if(a==0) return b==0?1:-1;

	mp.clear();

	ll M=ceil(pow(p*1.0,0.5)),t=1,s=qpow(a,M,p),k;

	for(int i=0;i<=M;++i) mp.insert(b,i),b=b*a%p;

	for(int i=1;i<=M;++i) if(t=t*s%p,(k=mp.find(t))!=-1) return i*M-k;

	return -1;

}

int main(){

	ll a,b,p,ans;

	while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF) {

		ans=BSGS(a%p,b%p,p);

		ans==-1?puts("no solution"):printf("%lld\n",ans);

	}

	return 0;

}

巴特西

【算法】BSGS算法

BSGS算法

Code(POJ2417 Discrete Logging)：

最新文章

热门文章