簡介
大步小步(Baby Step Giant Step)演算法，可以在 \(O(\sqrt{p}\cdot f(p))\) 的時間復雜度內（\(f(p)\) 為一個大小為 \(p\) 的映射結構（如 map、hash table）進行單次讀取 / 隨機訪問 的時間復雜度）內解下列關于 \(x\) 的方程（離散對數方程）：
\[a^{x}\equiv b\pmod{p} \]其中 \(\mathbf{p\in\mathbb{P},a\perp p}\)，
思路
由于歐拉定理 \(a\perp p,a^{b}\equiv a^{b\bmod \varphi(p)}\pmod{p}\)，可以得到：
\[a^{x \bmod (p-1)}\equiv a^{x}\pmod{p} \]因此我們有一個 \(O(p)\) 的演算法，但這還不夠，
考慮以 \(B=O(\sqrt{p})\) 為塊長分塊，令解 \(x=iB-j\)，則：
\[\begin{aligned} &a^{iB+j}\equiv b\pmod{p}\\ &(a^{B})^{i}\div a^{j}\equiv b\pmod{p}\\ &\because a\perp p\\ &\therefore(a^{B})^{i}\equiv a^{j}b\pmod{p} \end{aligned} \]然后，我們用一個映射結構記錄一下 \(a^{j}\bmod p\) 對應的 \(j\)，然后列舉 \(i\) 找映射里有沒有 \(((a^{B})^{i}\cdot b^{-1})\bmod p\) 即可，找逆元可以用費馬小定理，
P3846 [TJOI2007] 可愛的質數/【模板】BSGS
模板題，不解釋，
#include<bits/stdc++.h>
#define int long long
using namespace std;
int pow(int a,int b,const int &mod){
int ans=1;
for(;b;b>>=1,a=1ll*a*a%mod){
if(b&1)ans=1ll*ans*a%mod;
}
return ans;
}
int BSGS(int a,int b,const int &p){
int blk=sqrt(p);
map<int,int> mmap;mmap[1]=0;
int apw=1;
for(int i=1;i<=blk;i++){
apw=apw*a%p;
mmap[apw]=i;
}
int pw=1,Q=pow(a,blk,p),invb=pow(b,p-2,p);
for(int i=1;i<=blk;i++){
pw=pw*Q%p;
if(mmap.count(pw*invb%p)) return i*blk-mmap[pw*invb%p];
}
return -1;
}
signed main(){
int p,b,n;
cin>>p>>b>>n;
int ret=BSGS(b,n,p);
if(ret==-1) cout<<"no solution";
else cout<<ret;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554075.html
標籤：其他
下一篇：返回列表