【数论】BSGS

BSGS(baby-step giant-step)

学习资料：OI Wiki

基础篇

BSGS (baby-step giant step)，常用于求解离散对数问题，该算法可以在 (mathcal{O(sqrt p)}) 的时间内求解

[a^x equiv bquad (mod;p) ]

其中 (a\,ot\,p) 。方程的解 (x) 满足 (0le x<p)。

算法描述

令 (x=A[sqrt p]-B)，其中 (0le A,Ble lceil sqrt p ceil) ，则有

[a^{Alceilsqrt p ceil -B}equiv b;(mod\,p) ]

稍加变换，则有

[a^{Alceilsqrt p ceil}equiv ba^B;(mod\,p) ]

。

我们已知的是 (a,b)，所以我们可以先算出等式右边的 (ba^B) 的所有取值，枚举 (B)，用 hash / map 存下来，然后逐一计算 (a^{Alceilsqrt p ceil}) ，枚举 (A) ，寻找是否有与之相等的 (ba^B) ，从而我们可以得到所有的 (x)，(x=Alceilsqrt p ceil-B) 。

注意到 (A,B) 均小于 (lceilsqrt p ceil)，所以时间复杂度为 (mathcal{Q(sqrt p)})，用 map 则多用一个 (log) 。

扩展篇

接下来我们求解

[a^xequiv bquad(mod;p) ]

其中 (a,p) 不一定互质。

具体地，设 (d_1=gcd(a,p)) 。如果 (d_1 mid b) ，则原方程误解。否则我们把方程除以 (d_1) ，得到

[frac{a}{d_1}cdot a^{x-1}equivfrac{b}{d_1}quad(mod;frac{p}{d_1}) ]

如果 (a) 和 (frac{p}{d_1}) 仍不互质就再除，设 (d_2=gcd(a,frac{p}{d_1})) 。如果 (d_2 mid frac{p}{d_1}) ，则方程无解；否则同时除以 (d_2) 得到

[frac{a^2}{d_1d_2}cdot a^{x-2}equivfrac{b}{d_1d_2}quad(mod;p) ]

同理，这样不停判断下去直到 (aotfrac{p}{d_1d_2cdots d_k}) 。

记 (D=prod^k_{i=1}d_i) ，于是方程就变成了这样：

[frac{a^k}Dcdot a^{x-k}equivfrac bDquad(mod;frac pD) ]

由于 (aot frac pD) ，于是推出 (frac{a^k}Dotfrac pD) 。这样 (frac{a^k}D) 就有逆元了，于是把它丢到方程右边，这就是一个普通的 BSGS 问题了，于是求解 (x-k) 后再加上 (k) 就是原方程的解。

注意，不排除解小于等于 (k) 的情况，所以在消因子之前做一下 (mathcal{O(k)}) 枚举，直接验证 (a^iequiv b;(mod\,p)) ，这样就能避免这种情况。

BSGS && exBSGS 模板

luoguP4195

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll kpow(ll a,int b,int p){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return a;}
    ll g=exgcd(b,a%b,x,y);
    ll t=x;x=y;
    y=t-a/b*y;
    return g;
}
ll inv(ll a,ll p)//exgcd求逆元， 前提 gcd(a,p)==1
{
    ll x,y;
    exgcd(a,p,x,y);
    x=(x+p)%p;
    if(!x)x+=p;
    return x;
}
map<int,int>mp;
int BSGS(ll a,ll b,ll p)// gcd(a,p)==1
{
    a%=p;b%=p;
    int sp=ceil(sqrt(p));
    ll pa=b,ap=kpow(a,sp,p);mp.clear();
    for(int i=0;i<sp;i++,pa=pa*a%p)mp[pa]=i;
    pa=1;
    for(int i=0,j=0;i<=sp;i++,pa=pa*ap%p,j+=sp)
        if(mp.count(pa)&&j-mp[pa]>=0)return j-mp[pa];
    return -1;
}
int exBSGS(ll a,ll b,ll p)
{
    a%=p;b%=p;
    int k=0,t;ll tp=p,tb=b,ta=1;
    while((t=__gcd(a,tp))!=1){
        if(tb%t)return -1;
        tp/=t,tb/=t,ta=ta*a/t%tp;k++;
    }
    for(int i=0;i<=k;i++)
        if(kpow(a,i,p)==b)return i;
    tb=tb*inv(ta,tp)%tp;
    return BSGS(a,tb,tp)+k;
}
int main()
{
    ll a,b,p;
    while(scanf("%lld%lld%lld",&a,&p,&b)&&(a||b||p))
    {
        int res=exBSGS(a,b,p);
        if(res==-1)puts("No Solution");
        else printf("%d
",res);
    }
}