算法学习之BSGS(大步小步)及其扩展

本文主要是介绍算法学习之BSGS(大步小步)及其扩展，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

BSGS

大步小步算法,也称拔山盖世算法...

求解 : $\tiny \dpi{200} \tiny A^x \equiv B (mod P)$ 已知 A,B,P得情况下,求解x

分为普通情况和扩栈情况.

1.先说普通情况,

P是素数(确定的) $\tiny A^P = 1$ , 或 P为非素数但 , $gcd(A,P) = 1$ ,A,P, 互质时

开始之前先证明一个结论:

如果 $\tiny A^P = 1$ ，那么对于x∈N，有 $\tiny A^{x mod {\varphi(p)}} \equiv A^x(mod P)$ 也就是费马小定理.
证明：因为 $\tiny A^P = 1$ ，根据欧拉定理，得 $\tiny A^{\varphi (P)} \equiv 1 (mod P)$
设k∈N，根据同幂性，得 $\tiny A^{k*\varphi (P)} \equiv 1(mod P)$
设a∈N且a<φ(P)，所以 $\tiny A^{k*\varphi (P)+a} \equiv A^a(mod P)$
即 $\tiny A^{x mod {\varphi(p)}} \equiv A^x(mod P)$ ，得证。

将 x 分块成 i*m - j m = $\tiny \left \lceil \sqrt{p} \right \rceil$ = sqrt(p) + 1;

< $\tiny 0 \leq j <\left \lceil \sqrt{p} \right \rceil$ ;

$\tiny 0 \leq i < \left \lceil \sqrt{p} \right \rceil +1$ 然后就化简成了 : $\tiny A^{i*m} \equiv A^j*B (mod P)$

然后可以枚举[0-m] 将 $\tiny A^j*B$ 存入哈希表中.然后枚举[1,m] 查询哈希表中是否有 $\tiny A^{i*m}$

如果有, 则 x = i*m - hash[ $\tiny A^j*B$ ]

注意: [0−m]枚举j，而从[1−m]枚举i 的原因是: i不能为0，否则i*m−j有可能出现负数的情况

模板题:

bzoj 5296 [Cqoi2018]破解D-H协议

这道题: 已知 g,p g是p 的原根, 则 g^p = 1; 求 $\tiny g^{ab} (mod P)$ , 则只需要求解 $\tiny g^a \equiv A (mod P)$ ,a

然后求 B^a 就是 $\tiny g^{ab} (mod P)$

可以预处里 $\tiny g^j$ [0-m] 然后,求解 $\tiny g^{j*B}$ 时呈上一个逆元 A 在进行判断[

[代码]:

#include <iostream>
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i =n;i>=a;i--)
#define Si(x) scanf("%d",&x)//BSGS 算法
typedef long long ll;
const int maxn = 1e5+10;
const int mod = 1e9+7;
using namespace std;map<ll,int>hashs;ll n,p,g,A,B;
int bl;
ll  qpow(ll a,ll n)
{ll res = 1;for(;n;n>>=1){if(n&1)res = res*a %p;a = a*a %p;}return res;
}
void init()
{hashs.clear();bl = sqrt(p)+1;ll ans  = 1 ;for(int i = 0 ; i <= bl;i++){if(i==0){hashs[g%p] = i;continue;}ans = ans*g % p;hashs[ans] = i;}
}
void solve()
{cin>>A>>B;ll a;ll base = qpow(g,bl);ll temp = qpow(A,p-2);for(int i = 1 ;i <= bl ;i++){temp = temp*base%p;if( hashs[temp]){a = i*bl - hashs[temp];break;}}B = qpow(B,a);cout<<B<<endl;
}
int main()
{cin>>g>>p>>n;init();while(n--){solve();}return 0;
}

2.扩展BSBG

gcd(A,P)!=1 此时, 我们要想办法把方程转化成gcd(P,A) = 1

方程改写成: $\tiny A^x + kP = B, k \in Z$ ;

设 g = gcd(A,P) 如果 g 不能整出B, 则方程无解, 当可以整出时两边同时整出g

得 : $\tiny \frac{A}{g} A^{x-1} + k\frac{P}{g} = \frac{B}{g} , k \in Z$ ; 消去一个因子后得到方程: $\tiny \frac{A}{g} A^{x-1} \equiv \frac{B}{g} (mod \frac{P}{g})$

令 : $\tiny P' = \frac{P}{g}, B' = \frac{B}{g}({\frac{A}{g}})^{-1}$

得到新的方程: $\tiny A^{x'} \equiv B' (mod P'); x = x'+1$

不断重复这个过程最后一定会得到一个可以解的方程，套用刚刚的BSBG解出后即可。

要注意的是在这个过程中如果某一步发现 $\tiny B' = 1$ ，那么就可以直接退出，因为这时候已经得到解了.

注意:整出g得时候肯会出现多次,所以要记录cnt

代码:

inline ll qpow(ll a,ll n,ll p)
{ll res = 1;for(;n;n>>=1){if(n&1) res = res*a %p;a = a*a%p;}return res;
}
int BSBG(ll a,ll b,ll p) // -1 no answer
{a%=p,b%=p;if(b==1) return 0;int cnt = 0;ll t = 1;for(int g = __gcd(a,p); g!=1; g = __gcd(a,p)){if(b%g) return -1;// no answerp/=g,b/=g,t = t*a/g%p;++cnt;if(b==t) return cnt; }map<ll,ll>Hashs;int m = sqrt(p) +1;ll base = b;for(int i = 0 ; i<=m;i++){Hashs[base]  = i;base = base*a%p;}base = qpow(a,m,p);ll now = t;for(int i = 1;i<=m+1;i++){now = now *base %p;if( Hashs[now]){return i*m-Hashs[now] +cnt;}}return -1;
}

这篇关于算法学习之BSGS(大步小步)及其扩展的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！