浅谈BSGS算法

gyyyyx · 2024-04-05 17:30:33 · 算法·理论

BSGS算法（baby-step giant-step），又称大步小步。

用于解决这样一个同余方程：a^x\equiv b\pmod P。

众所周知，形似 ax\equiv b\pmod P 的同余方程我们可以用快速幂（费马小定理）或者扩展欧几里得（exgcd）求逆元来解。

而对于指数的同余方程，我们可以根据根号分治是思想处理。

我们令 x=A\lfloor\sqrt{P}\rfloor-B，其中 0\leq A,B\leq\lfloor P\rfloor。

将其带回原式：

移项：

由于 A,B 均是 O(\sqrt{n}) 的大小，我们可以直接枚举 A,B，然后判断是否存在 A,B 满足同余式。

具体地，我们可以先枚举 B，然后将所有 ba^B 存入 hash 表里，然后枚举 A，判断是否 hash 表里是否有 a^{A\lfloor\sqrt{P}\rfloor}。

而如果枚举到最后都没有 A 满足条件，则说明无解。

一般题目都是要求输出最小解，因此找最小的 A 和最大的 B 即可。

板，码：

inline LL bsgs(LL a,LL b,LL p){
    map <LL,LL> mp;
    int t(sqrt(p)+0.5);
    LL res(1);
    for(int B(1);B<=t;++B){
        res=res*a%p;
        mp[b*res%p]=B;
    }
    LL cur(res);
    for(int A(1);A<=t;++A){
        if(mp[cur]) return 1ll*A*t-mp[cur];
        cur=cur*res%p;
    }
    return -1;
}