菜鸟头条

大步小步(BSGS)算法学习笔记

2023-06-01 13:22 由 xiezheyuan 发表于 #其他

简介

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

热门相关：斗神战帝   最强反套路系统   战神   重生之至尊千金   战神