「算法笔记」BSGS

$\text{BSGS}$ 用于解决高次同余方程的最小整数解,主要思想是分块。


引入

求出下面方程的最小非负整数解 $x$:

$$ a^x\equiv b\pmod p\quad (\gcd(a,p)=1) $$

此处的未知数 $x$ 在指数上,我们就要用到 $\text{BSGS}$(大步小步法,即 $\text{Baby Step Giant Step}$)算法。


思想

$\text{BSGS}$ 的本质是分块的思想,我们设 $m=\left\lceil\sqrt p\right\rceil$(注意是上取整),又设 $x=i\times m-j$,其中 $0\le i\le m,0\le j < m$;我们可以将原方程转化为:

$$ a^{i\times m-j}\equiv b\pmod p $$

在 $x=i\times m-j​$ 中,$i​$ 即为大步,$j​$ 即为小步;我们将 $j​$ 移到方程的右边得到:

$$ a^{i\times m}\equiv b\times a^j\pmod p $$

观察到 $j​$ 只有 $\mathcal O(m)​$ 种取值,所以我们对于每个 $j​$,把 $b\times a^j\bmod p​$ 的值记录下来,存放在哈希表中(有没有一种分块打表的感觉?)。然后枚举左半边的 $i​$,将对应的值在哈希表中查找对应的 $j​$,如果能找到对应的 $j​$ 那么说明已经找到答案了。

对于插入哈希表中的 $j$ 的值,显然在同一个值时,$j$ 的值越大越好,那么直接覆盖即可,无需关注细节问题!

注意:代码中必须要判断无解情况!(本来就无解,或者没有找到合法解)

时间复杂度:$\mathcal O(\sqrt p)$


代码

int BSGS(int a, int b, int P) {
    if (b % gcd(a, P)) return -1;
    a %= P, b %= P, mp.clear();
    int m = ceil(sqrt(P));
    for (int i = 0; i <= m; i++, b = 1LL * b * a % P) mp[b] = i;
    a = pow(a, m, p);
    for (int i = 0, j = 1; i <= m; i++, j = 1LL * j * a % P) {
        if (mp.count(j) && i * m >= mp[j]) return i * m - mp[j];
    }
    return -1;
}

习题

发表评论