BSGS | Virgil's Blog

离散对数问题

有一类问题形式如下：

给定同余方程 $a^x\equiv b\quad(\mod m)$ ，求其最小解。

这样的方程解起来并不简单，最暴力的想法自然是一个一个试，于是对于这类“不可做”问题考虑分块的做法。下面我们将分两种情况讨论：

$(a,m)=1$

$a$ 和 $m$ 互质的情况下问题就比较好处理了。

设 $x=A\sqrt m+B$

则原来方程可化为：
$$
\begin{aligned}
a^{A\sqrt m +B}&\equiv b\quad(\mod m)\
\implies
a^B&\equiv ba^{-A\sqrt m}\quad(\mod m)
\end{aligned}
$$
于是我们把 $a^B$ 存入哈希表中，然后 $O(\sqrt n)$ 找到 $A$ 的取值。

Discrete Logging

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using std::ceil;
using std::sqrt;
typedef long long ll;
int qpow(int a,int x,int p)
{
	int res=1;
	for(;x;x>>=1,a=(ll)a*a%p)
		if(x&1) res=(ll)res*a%p;
	return res;
}

std::map<int,int> mp;
int BSGS(int a,int b,int p)
{
	mp.clear();
	int i,sp=ceil(sqrt(p));
	int aB=1;mp[aB]=0;
	int aspInv=qpow(qpow(a,sp,p),p-2,p);
	for(i=1;i<sp;i++)
	{
		aB=(ll)aB*a%p;
		if(!mp.count(aB)) mp[aB]=i;
	}
	for(i=0;i<=sp;i++)
	{
		if(mp.count(b)) return i*sp+mp[b];
		b=(ll)b*aspInv%p;
	}
	return -1;
}

int main()
{
	int a,b,p,ans;
	while(~scanf("%d%d%d",&p,&a,&b))	
	{
		if(~(ans=BSGS(a,b,p))) printf("%d\n",ans);
		else puts("no solution");
	}
	return 0;
}

[SDOI2011] 计算器

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
using std::ceil;
using std::sqrt;
typedef long long ll;

int qpow(int a,int x,int p)
{
	int res=1;
	for(;x;x>>=1,a=(ll)a*a%p)
		if(x&1) res=(ll)res*a%p;
	return res;
}

std::map<int,int> mp;
int BSGS(int a,int b,int p)
{
	if(!a) return b?-1:1;
	mp.clear();
	int i,sp=ceil(sqrt(p));
	int aB=1;mp[aB]=0;
	int aspInv=qpow(qpow(a,sp,p),p-2,p);
	for(i=1;i<sp;i++)
	{
		aB=(ll)aB*a%p;
		if(!mp.count(aB)) mp[aB]=i;
	}
	for(i=0;i<=sp;i++)
	{
		if(mp.count(b)) return i*sp+mp[b];
		b=(ll)b*aspInv%p;
	}
	return -1;
}

int main()
{
	int T,K;scanf("%d%d",&T,&K);
	while(T--)
	{
		int a,b,p,ans;scanf("%d%d%d",&a,&b,&p);
		a%=p;
		switch(K)
		{
			case 1:printf("%d\n",qpow(a,b,p));break;
			case 2:
				   b%=p;
				   if(!a&&b) puts("Orz, I cannot find x!");
				   else printf("%d\n",int((ll)b*qpow(a,p-2,p)%p));
				   break;
			case 3:
				   b%=p;
				   if(~(ans=BSGS(a,b,p))) printf("%d\n",ans);
				   else puts("Orz, I cannot find x!");
				   break;
		}
	}
	return 0;
}

$(a,m)\neq1$

我们既然已经有了 $a$ 和 $m$ 互质情况下的做法，那只需要将 $a$ 和 $m$ 化为互质的即可。

对于 $a^x\equiv b\quad(\mod m)$ 设 $(a,m)=g$

如果 $g\not\mid b$ 那么无解。

如果 $g\mid b$ 那么原方程可化为 $(a’g)^x\equiv b’g\quad(\mod m’g)$

同余式两边同除以 $g$ 得： $(a’)^{x-1}\equiv b’(a’)^{-1}\quad(\mod m’)$

注意每次新的 $x$ 都是原来的 $x-1$ ，故需要记录操作次数 $cnt$

如果 $b’(a’)^{-1}\equiv1\quad(\mod m’)$ 或 $m’=1$ 则解为 $cnt$

不断执行上述操作，直至 $(a,m)=1$

注意特判 $a\equiv0\quad(\mod m)$ 时的情况

[SPOJ] Mod

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
using std::ceil;
using std::sqrt;
typedef long long ll;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
void exgcd(int a,int b,int &x,int &y)
{
	if(!b) {x=1,y=0;return;}
	exgcd(b,a%b,y,x);y-=x*(a/b);
}
int inv(int a,int p){int x,y;exgcd(a,p,x,y);return (x%p+p)%p;}

int qpow(int a,int x,int p)
{
	int res=1;
	for(;x;x>>=1,a=(ll)a*a%p)
		if(x&1) res=(ll)res*a%p;
	return res;
}

std::map<int,int> mp;
int BSGS(int a,int b,int p)
{
	a%=p,b%=p;
	if(!a) return b?-1:1;
	int cnt=0;
	for(int g=gcd(a,p);g>1;g=gcd(a,p))
	{
		if(b%g) return -1;
		b/=g,p/=g;b=(ll)b*inv(a/g,p)%p;
		cnt++;
		if(b==1) return cnt;
	}
	if(p==1) return cnt;

	mp.clear();
	int i,sp=ceil(sqrt(p));
	int aB=1;mp[aB]=0;
	int aspInv=inv(qpow(a,sp,p),p);
	for(i=1;i<sp;i++)
	{
		aB=(ll)aB*a%p;
		if(!mp.count(aB)) mp[aB]=i;
	}
	for(i=0;i<=sp;i++)
	{
		if(mp.count(b)) return i*sp+mp[b]+cnt;
		b=(ll)b*aspInv%p;
	}
	return -1;
}

int main()
{
	int a,b,p,ans;
	while(scanf("%d%d%d",&a,&p,&b)&&p)
	{
		if(~(ans=BSGS(a,b,p))) printf("%d\n",ans);
		else puts("No Solution");
	}
	return 0;
}