大步小步算法

大步小步算法（baby step giant step，BSGS）

是一种用来求解离散对数（即模意义下对数）的算法，即给出 \(a^x \equiv b \pmod m\) 中\(a,b,m\) 的值（这里保证 \(a\) 和 \(m\) 互质，求解 \(m\)

既然保证了 \(a\) 和 \(m\) 互质，那么很容易联想到欧拉定理，我们知道 \(a^{\phi(m)} \equiv 1 \pmod m\)，也就说明 \(a^x\) 在模 \(m\) 意义下有一个长度为 \(\phi(m)\) 的循环节。既然后面都是循环的，我们只需要考虑 $x\leq\phi(m) $ 的情形就可以了。这就有了离散对数的朴素算法：暴力枚举。复杂度 \(O(\phi(m))\)，因为当 \(m\) 是质数时 \(\phi(m)=m-1\) ，最坏时间复杂度就是 \(O(m)\) 。

实际上，大步小步算法就是对暴力枚举的一个简单的改进, 我们把 \(x\) 拆成 \(At-B\) ，则原式化为 \(a^{At-B} \equiv b \pmod m\) ，即 \(a^{At} \equiv ba^B \pmod m\) 。然后我们预计算出右侧所有可能的取值，再固定一个 \(t\) ，计算出左边可能的值，当发现某个值已经在右边出现过，这时的 \(At-B\) 就是我们要求的 \(x\) 。

B可能的取值有 \(\phi(m) \:\: mod \:\: t\) 个，A可能的取值有 \(\lfloor \frac{\phi(m)}{t} \rfloor\) 个，不难看出，取 \(t= \lceil \sqrt {\phi(m)} \rceil\) 是最好的，当然为了避免计算欧拉函数，我们直接取 \(t=\lceil \sqrt{m} \rceil\) ，不难验证，此时取 $A,B\in [1,t] $ 可以保证把 \(x\in[1,m-1]\) 全部枚举一遍。时间复杂度为 \(O(\sqrt m)\)

ll bsgs(ll a,ll b, ll m, ll k = 1){
	unordered_map<ll, ll>hs;
	ll cur=1,t=sqrt(m)+1;
	for(int B=1;B<=t;B++){
		(cur*=a)%=m;
		hs[b*cur%m]=B; // 哈希表中存B的值
	}
	ll now=cur*k%m;
	for(int A=1;A<=t;A++){
		auto it=hs.find(now);
		if(it!=hs.end())return A*t - it->second;
		(now*=cur)%=m;
	}
	return -inf; 
}

例题

1.G - Sequence in mod P
题意

p是质数

题解：
不妨设 \(i=A*t-B, f(X)=(aX+b)%P\)
根据题目
\(f^{At-B}(S) \equiv G \pmod P \Rightarrow f^{At}(S)\equiv f^B(G) \pmod P\)
因此我们只要取 \(t=\lceil \sqrt P \rceil\) 来进行大步小步算法
如何计算\(f^t(X)\)，因为递归是线性的，设 \(f^t(X)=A^{(t)}X+B^{(t)}\)
由递归式可知
\(A^{(t)} = A^{(t-1)}*a\)
\(B^{(t)} = a*B^{(t-1)}+b\)

#include <bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define YES {puts("-1");return;}
#define NO {puts("NO");return ;}
using namespace std;
const int maxn=5e5+101;
const int MOD=998244353;
const int inf=2147483647;
const double pi=acos(-1);
const double eps=1e-12;

ll read(){
    ll x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x*f;
}

void solve(){
	ll p=read(),a=read(),b=read(),s=read(),g=read();
	ll ans=-1;
	if(s==g){puts("0");return ;}
	if(a==0){
		if(b==g)puts("1");
		else puts("-1");
		return ;
	}
	ll aa=1,bb=0,cur=g,t=sqrt(p)+1;
	unordered_map<ll,ll>hs;
	for(int B=1;B<=t;B++){
		aa=aa*a%p;
		bb=(bb*a+b)%p;
		cur=(cur*a+b)%p;
		hs[cur]=B;
	}
	cur=(aa*s+bb)%p; 
	for(int A=1;A<=t;A++){
		if(hs.count(cur)){
			ans=A*t-hs[cur];
			break;
		}
		cur=(aa*cur+bb)%p;
	}
	printf("%lld\n",ans);
	return ;
}
int main(){
	int t=read();
	while(t--)solve();
    return 0;
}