BSGS算法

离散对数问题

假设有一个同余方程a^x \equiv b \pmod m，其中a,b,m都是给定的整数，a与m互素。如何求解x的值？

第一个想法可能是暴力枚举，将x从0开始枚举到m-1，直到找到一个满足方程的x。时间复杂度是O(m)，如果m很大就挂了。

BSGS算法

既然暴力不行，那么我们就要想办法降低时间复杂度。BSGS算法就是一种优化的算法，它的时间复杂度是O(\sqrt{m})。它的思想也很简单。

首先我们令x=A\sqrt{m}-B，其中A,B是两个整数且0\leq A,B\leq \sqrt{m}。那么原方程就变成了a^{A\sqrt{m}-B} \equiv b \pmod m，即a^{A\sqrt{m}} \equiv b\cdot a^B \pmod m。

我们可以将方程分解为两个方程:

对于第一个方程，我们可以从1到\sqrt{m}枚举B的值，用一个map存对应B的值。对于第二个方程，依旧从0到\sqrt{m}枚举A的值，然后在map中查找是否有相等的b\cdot a^B，获取B的值，最后得到x的值。

//a^x=b(mod p)
LLI BSGS(int a,int b,int p){
	if(a%p==0||b%p==0){//特殊情况
		if(b%p==0&&a%p==0)return 1;
		else return -1;
	}

	map<LLI,LLI> mp;
	LLI cur=1,t=sqrt(p)+1;
	for(LLI B=1;B<=t;++B){
		cur=cur*a%p;
		mp[b*cur%p]=B;
	}
	LLI now=cur;
	for(LLI A=1;A<=t;++A){
		if(mp[now])return A*t-mp[now];
		now=now*cur%p;
	}return -1;
}