大步小步(BSGS)算法学习笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了大步小步(BSGS)算法学习笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

简介

大步小步(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

模板题，不解释。文章来源地址https://www.toymoban.com/news/detail-467062.html

#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;
}

到了这里，关于大步小步(BSGS)算法学习笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！