大步小步算法(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;
}