数论——求a^x ==b(mod p)中的x————bsgs算法（1.0模板）[个人笔记]

小咪咪 2024-04-18 23:43 40阅读 0赞

#### bsgs算法： ####

bsgs算法，又称大小步算法。

用来解决**ax == b(mod c)**，求x的问题。  
**其中a，b， c是整数， c是质数， 且a不是c的倍数。**

#### 过程： ####

将**x == i\*m -j**， 其中**m = ceil(sqrt©)**;

所以：**ai\*m-j == b(mod c)**  
就等于**ai\*m == b \* aj(mod)c**;

因此就可以枚举出j所有可能的结果存入map中；（存法， map<b \* aj,j>）  
然后枚举i就行。  
**注：**  
为什么 m = ceil（sqrt( c )）；  
如果x = i\*m-j， x最大是c  
为什么x不会大于c？  
根据欧拉降幂 ax == b(mod c) 等价于 ax%（∮( c )） == b(mod c), 因为c是素数所以 ∮( c ) = c-1；  
因此 x不会大于c

ll qpow(ll a, ll n, ll mod);// 快速幂
    ll bsgs(ll a, ll b, ll mod)
    { 
        map<ll ,ll>mp;//<b*a^指数， 指数>
        mp.clear();
        if(a%mod == 0)return -2;// a是mod的倍数 不满足bsgs的条件， 算不出答案
        ll m = ceil(sqrt(mod*1.0)); //sqrt(mod) 向上取整
    
        ll ans;
        for(ll j = 0;j <= m;j++)// 枚举j， 将b*a^j 存入 map中
        { 
            if(j == 0)
            { 
                ans = b%mod;
                mp[ans] = j;
                continue;
            }
    
            ans = ans*a%mod;
            mp[ans] = j;
    
        }
    
        ll t = qpow(a, m, mod);
         ans = 1;
        for(int i = 1;i <= m;i++)
        { 
            ans = (ans*t)%mod;
            if(mp.count(ans))// 如果存在a^i*m === b*a^j
            { 
            	ll ret = i*m-mp[ans];//
            	return (ret%mod+mod)%mod;
            }
        }
    
        return -2;//没有答案
    }
    
    
    ll qpow(ll a, ll n, ll mod)// 快速幂
    { 
        ll ret = 1;
        while(n)
        { 
            if(n%2)ret = ret*a%mod;
            a = a*a%mod;
            n/=2;
        }
        return ret;
    }

##### 当然也可以看成x == i\*m+j， 不过这个需要求逆元： #####

ll qpow(ll a, ll n, ll mod)
    { 
        ll ret = 1;
        while(n)
        { 
            if(n%2)ret = ret*a%mod;
            a = a*a%mod;
            n/=2;
        }
        return ret;
    }
    
    ll bsgs(ll a,ll b, ll mod)// 求a^x == b
    { 
        ll m = ceil(sqrt((double)Mod));// 向下取整
        map<ll,ll> mp;// <a^指数, 指数>
        mp[1] = 0;// a的0次幂
        ll ans = 1;
        for(int i = 1; i <= m; i++)
        { 
            ans = ans*a%mod;
            if(!mp.count(ans)) mp[ans] = i;//该数不存在 就记录
        }
        ll pm = qpow(qpow(a,m, mod), mod-2, mod);// a^m 的逆
    
        for(int i = 0; i <= m; i++)
        { 
            if(mp.count(b)) return i*m+mp[b];
            b = b*pm%mod;
        }
    }