BSGS 算法

定义

BSGS 算法用于求解关于\(x\)的方程\(a^x\equiv b\pmod p\)的解。

求解算法

思路与简单证明

方程有解的充要条件是\(p\)质数且\((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\)；

于是我们从\(0\sim m\)枚举\(j\)，将\(ba^j\)的结果存入 hash 表中。

然后从\(1\sim m\)枚举\(i\)，在 hash 表中查找\(a^{im}\)的值，如果存在，返回答案为\(im-j\)。

方程有解条件和\(m\)取值的讨论：证明：\(a^{k\bmod p-1}\equiv a^k\pmod p\)：

\[a^{k\bmod p-1}\equiv a^{k-t(p-1)}\equiv \frac{a^k}{a^{t(p-1)}}\pmod p\]

当且仅当\(p\)质数且\((a,p)=1\)时，\(a^{t(p-1)}\equiv a^{p-1}\equiv 1\pmod p\)； 此时\(a^{k\bmod p-1}\equiv a^k\pmod p\)。

实现

map<LL,LL>tab;
LL BSGS(LL y,LL z,LL p)
{
    y%=p;z%=p;
    tab.clear();
    LL m=ceil(sqrt(p));
    if(!y)
    {
        if(!z)return 1;
        else return -1;
    }
    else if(z==1)return 0;
    LL k=z%p,temp=qpow(y,m,p);
    tab[z]=m;
    for(LL j=1;j<m;++j)
    {
        k=k*y%p;
        if(!tab[k])tab[k]=j;
    }
    k=1;
    for(LL i=1;i<=m+1;++i)
    {
        k=k*temp%p;
        if(tab[k])return i*m-(tab[k]%m);
    }
    return -1;
}

扩展

思路与简单证明

对于\(p\)不为质数的情况，设\(d=(a,b)\)，于是\(a=Ad,b=Bd,c=Cd\)，得：

\[(Ad)^x\equiv Bd\bmod Cd\]

同除\(d\)，得\(A\cdot(Ad)^{x-1}\equiv B\pmod C\)

执行多次消除因子后，得\(D\cdot A^{x-cnt}\equiv B\pmod C\)；

令\(x=im-j+cnt\)，\(cnt\)为消除因子的次数，剩下和普通 BSGS 相同。

但是注意到存在\(x\leq cnt\)的情况，在消除因子时特判即可。

实现

LL exBSGS(LL y,LL z,LL p)
{
    y%=p;z%=p;
    tab.clear();
    if(!y)
    {
        if(!z)return 1;
        return -1;
    }
    else if(z==1)return 0;
    LL t,cnt=0,d=1;
    while((t=gcd(y,p))!=1)
    {
        if(z%t)return -1;
        ++cnt,z/=t,p/=t,d=d*(y/t)%p;
        if(z==d)return cnt;
    }
    LL m=ceil(sqrt(p));
    LL k=z%p;t=qpow(y,m,p);
    tab[z]=m;
    for(LL j=1;j<m;++j)
    {
        k=k*y%p;
        tab[k]=j;
    }
    for(LL i=1;i<=m+1;++i)
    {
        d=d*t%p;
        if(tab[d])return i*m-(tab[d]%m)+cnt;
    }
    return -1;
}