BSGS算法

BSGS算法是一种用于解决离散对数问题的算法，它的全称是Baby Step Giant Step，意为小步大步。然而我并不知到为什么要叫这个名字

离散对数问题

假设有一个同余方程$a^x\equiv b(\mathrm{mod}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\le A,B\le \sqrt{m}$。那么原方程就变成了$a^{A\sqrt{m}-B}\equiv b(\mathrm{mod}m)$，即$a^{A\sqrt{m}}\equiv b\cdot a^B(\mathrm{mod}m)$。

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

$$\{\begin{array}{l}c\equiv b\cdot a^B(\mathrm{mod}m)\\ a^{A\sqrt{m}}\equiv c(\mathrm{mod}m)\end{array}$$

对于第一个方程，我们可以从$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;
}