BSGS 与 exBSGS

· · 算法·理论

基础数学——BSGS 与 exBSGS

基础数论的最后一个简单算法了，再往后就是线性代数、若智多项式、生成函数以及各类式子变换了，祭奠我那逝去的基础数论。

BSGS

解决的问题 & 思路

全称 Baby-Step Giant-Step，用于求解高次同余方程（未知数在指数上）。

BSGS 算法可用于解决如下方程：

a^x\equiv b \pmod p

其中 \gcd(a,p)=1。

令 m=\lceil \sqrt{p} \rceil，我们将 x 写成 im-j 的形式，有：

a^{im-j}\equiv b \pmod p a^{im}\equiv ba^j \pmod p

将 j \in [0,m-1] 的 ba^j 放入一个哈希表中，再令 i\in [1,m]，从小到大枚举 i，求解出所有的 a^{im}，在哈希表中找对应的值，对于第一个 a^{im}\equiv ba^j \pmod p，则 im-j 即是我们要找的 x。

代码

P3846 [TJOI2007] 可爱的质数/【模板】BSGS代码如下。

#include <iostream>
#include <unordered_map>
#include <cmath>
#define ll long long
using namespace std;
// a^x=b(mod p)
ll ksm(ll a,ll b,ll p){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%p;
        b>>=1;
        a=a*a%p; 
    }
    return ret;
}
ll a,b,p;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>p>>a>>b;
    b%=p;
    ll m=ceil(sqrt(p));
    unordered_map<ll,ll> mp;
    mp.clear();
    ll ami=1;
    for(ll j=0;j<m;j++){
        if(!j) ami=1;
        else ami=ami*a%p;
        mp[b*ami%p]=j;
    }
    a=ksm(a,m,p);
    for(ll i=1;i<=m;i++){
        ami=ksm(a,i,p);
        if(mp.count(ami)!=0&&i*m-mp[ami]>=0){
            cout<<i*m-mp[ami];
            return 0;
        }
    }
    cout<<"no solution";
    return 0;
}

exBSGS / 扩展BSGS

最暴力的一集。

解决的问题 & 思路

普通 BSGS 无法解决底数与模数不互质的情况，那我们就强硬的把底数和模数变成是互质的不就行了。

详细的，我们有求解：

a^x\equiv b \pmod p

把该式转换形式：

a \cdot a^{x-1} \equiv b \pmod p a \cdot a^{x-1} + k \cdot p = b

当且仅当 \gcd(a,p) \mid b 时方程有解，设 g_1=\gcd(a,p)，有：

\frac{a}{g_1}a^{x-1}+\frac{p}{g_1}k=\frac{b}{g_1}

当且仅当 \gcd(a,\frac{p}{g_1}) \mid \frac{b}{g_1} 时方程有解。如果此时 \gcd(a,\frac{p}{g_1}) \ne1，我们依然无法用普通 BSGS 求解，设 g_2=\gcd(a,\frac{p}{g_1})，有：

\frac{a^2}{g_1}a^{x-2}+\frac{p}{g_1}k=\frac{b}{g_1} \frac{a^2}{g_1g_2}a^{x-2}+\frac{p}{g_1g_2}k=\frac{b}{g_1g_2}

重复上述操作 n 次，设 G=\prod_{i=1}^ng_i，我们有：

\frac{a^n}{G}a^{x-n}+\frac{p}{G}k=\frac{b}{G}

当 \gcd(a,\frac{p}{G})=1 时，上述不定方程等价变形为：

\frac{a^n}{G}a^{x-n} \equiv \frac{b}{G} \pmod{\frac{p}{G}}

跑普通的 BSGS 就好啦！

代码

P4195 【模板】扩展 BSGS/exBSGS代码如下。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}
ll ksm(ll a,ll b,ll p){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%p;
        b>>=1;
        a=a*a%p;
    }
    return ret;
}
ll exbsgs(ll a,ll b,ll p){
    a%=p,b%=p;
    if(b==1||p==1) return 0;
    ll d,k=0,A=1;
    while(1){
        d=gcd(a,p);
        if(d==1) break;
        if(b%d!=0) return -1;
        k++,b/=d,p/=d;
        A=A*(a/d)%p;
        //这里是真逆天，要先让 p 变小再更新 A 
        if(A==b) return k;
    }
    ll m=ceil(sqrt(p));
    ll baj=b,Aaxk=A;
    //Aaxk 要先设为 A 
    unordered_map<ll,ll> mp;
    mp.clear();
    mp[b]=0;
    for(ll i=1;i<m;i++){
        baj=baj*a%p;
        mp[baj]=i; 
    }
    ll ami=ksm(a,m,p);
    for(ll i=1;i<=m;i++){
        Aaxk=Aaxk*ami%p;
        if(mp.count(Aaxk)!=0){
            return i*m-mp[Aaxk]+k;
        }
    }
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ll a,p,b;
    while(1){
        cin>>a>>p>>b;
        if(!a&&!p&&!b) return 0;
        ll ans=exbsgs(a,b,p);
        if(ans==-1) cout<<"No Solution\n";
        else cout<<ans<<"\n";
    }
    return 0;
}