BSGS算法及其扩展算法

BSGS算法

所谓 Baby Step, Giant Step 算法，也就是暴力算法的优化

用于求出已知 $a, b, p$, 且 $p$ 为质数 时 $a^x \equiv b \pmod p$ 的一个最小正整数解 $x$

下文中 $a \perp p$ 指的是 $a, p$ 互质

有两种情况：

• $a, p$ 不互质，又由于 $p$ 是质数，意味着 $a$ 是 $p$ 的倍数，所以 $b$ 如果不为 $0$ ，那么一定无解

• 两者互质……即 $a \perp p$ :

考虑到 $a \perp p$ 意味着 $a$ 在 $p$ 的完全剩余系中，也就是说 $f(x) = a^x \pmod p$ 是一个周期为 |<a>| (……就是 $a$ 在模 $p$ 意义下的生成子群的大小) 的周期函数

实际上我们不会算出其周期的具体大小，我们只需要利用 |<a>| 恒 $\le p$ 就行了

那么我们只需要枚举 $x \in [0, p)$ 依次验证就可以求解了

但是暴力枚举没有那么优秀，对于出题人的数据可能过不了

所以我们就可以采用把毒瘤出题人吊起来打的方法BSGS算法进行优化

BSGS算法采用分块的思想 （分块？块大小就 $\sqrt p$ 不就就行了吗，有什么好疑惑的？

假设块大小为 $t$

先参入 $t$ 改写一下式子 $a^x \equiv b \pmod p$

得到 $a^{it-j} \equiv b \pmod p$

由于 $a \perp p$ ，上述式子等价于 $a^{it} \equiv (a^t)^i \equiv b a^j \pmod p$

那么我们先预处理右式，枚举 $j \in [0, t)$ 把 $ba^j \mod p$ 插入到一个Hash表中

也就是说 $HashMap: \quad ba^j\ mod\ p \Rightarrow j$

那么枚举 $i \in [0, \lceil \frac pt \rceil]$ 计算出 $a^{it} \mod p$ ，查找是否有对应的 $j$，更新答案即可

时间复杂度为 $O(t + \lceil \frac pt \rceil)$

为了进一步优化时间复杂度，已知均值不等式 $a + b \ge 2\sqrt{ab}$，当且仅当 $a=b$ 时等号成立，所以我们令 $t = \lceil \sqrt p \rceil$，那么时间复杂度就简化为了 $O(\sqrt p)$

常数为 $2$ 可能还需要带一个 $log$ ? QwQ

参考代码如下：仅供参考

template<typename data>
data BSGS(data a, data b, data p) {
    b %= p;
    static std::map<data, data> hash; hash.clear();
    data t = std::ceil(std::sqrt(p)), v(1), j(0);
    for (; j < t; ++j) {
        // 此时 v = a^j % p
        hash[v * b % p] = j;
        v = v * a % p;
    }

    // 把 a 预处理成 a^t, 这样 (a^t)^i 就可以更快的算出了
    a = qpow(a, t, p), v = 1;
    // 如果此时 a 已经为 0 了，由于 t < p， p为质数所以 p|a (a为p的倍数)
    // 那么此时，如果 b 不为 0 则一定无解
    if (a == 0) return b == 0 ? 1 : -1;

    for (data s(0); s <= t; ++s) {
        // 此时 v = (a^t)^s
        j = hash.find(v) == hash.end() ? -1 : hash[v];
        if (~j && s * t >= j) return s * t - j;
        v = v * a % p;
    }
    return -1;
}

扩展BSGS算法 (exBSGS)

其实问题一摸一样，只是 $p$ 不为质数了，也就是说其中 $a, p$ 不一定互质

那么我们需要想办法使之变得互质，然后通过普通的 BSGS 算法求解

具体的，令 $d_1 = gcd(a, p)$，如果 $d_1 \nmid b$ 则原方程无解

这个我们可以将同余式转换：$s a^x + tp = b$

左式再转化为 $d_1 (s a^{x-1} \frac a{d_1} + t \frac p {d_1}) = b$

也就是说，如果 $d_1 \nmid b$ ，那么一定无整数解

那么上述式子就可以转化为 $sa^{x-1} \frac a{d_1} + t \frac p {d_1} = \frac b {d_1}$

再换成同余式子，就变为了 $\frac a {d_1}\cdot a^{x-1} \equiv \frac b {d_1} \pmod {\frac p {d_1}}$

如果此时 $a$ 与 $\frac p {d_1}$ 任然不互质，那么继续上述转化，令$d_2 = gcd(a, \frac p {d_1})$

则 $\frac a {d_1 d_2} \cdot a^{x-2} \equiv \frac b {d_1 d_2} \pmod {\frac p {d_1 d_2}}$

同理不断处理，直到 $a \perp \frac p {d_1 d_2 \dots d_k}$

我们记 $D = \prod_{i = 1}^k d_i$

那么最终的方程就是 $\frac {a^k} {D} \cdot a^{x-k} \equiv \frac bD \pmod {\frac pD}$

这样，我们把 $\frac {a^k}D$ 通过逆元丢到方程右边，就成为了一个普通的 BSGS 问题了

注意一个细节，不排除解小于等于 $k$ 的情况，所以在消去 $d_i$ 的时候还要判断一下 $a^i \equiv b \pmod p$ 是否可行

还有一些细节问题我会放在代码之后解释

参考代码：仅供参考

// inv(i) i \equiv 1 mod p
// i * inv(i) + kp = 1 (kown i, p, 1)
template<typename T>
T inv(T i, T p) {
    T iv, k;
    exgcd(i, p, &iv, &k);
    iv %= p;
    // 注意点4
    return iv < 0 ? iv + p : iv;
}

data exBSGS(data a, data b, data p) {
    // 注意点 1 
    b %= p;
    // 注意点 2
    if (b == 1 || p == 1) return 0;
    data d, ak(1), k(0);
    while ((d = gcd(a, p)) != 1) {
        if (b % d) return -1;
        ++k, p /= d, b /= d;
        ak = a / d * ak % p;
        // 注意点 3
        if (ak == b) return k;
    }

    // 注意点 4
    b = b * inv(ak, p) % p;
    data res = BSGS(a, b, p);
    // 注意点 5
    if (~res) return res + k;
    return -1;
}

注意点1：为什么需要一次 b %= p

考虑这样一组数据 a = 10, b = 110, p = 100

其实这个地方也可以加一句 a %= p，可以减少部分运算，也不会影响正确性，反正都是乘法~~，模意义下人人平等~~

注意点2：这里的特判是什么意思

如果p为1，相当于同余式恒成立，所以直接返回最小答案即可

如果b为1，考虑到 $\forall a \ne 0, a^0 = 1$，所以直接返回最小答案即可

注意点3：这就是上文中答案小于 $k$ 情况的特判

注意点4：

由于是在模 $\frac pD$ 意义下，所以需要通过逆元的方式调整

但是考虑到两者不知道是否互质，所以通过扩展欧几里得算法就行了

扩展欧几里得算法可以参考：算法学习笔记(1): 欧几里得算法及其扩展

注意点5：

由于我们在求 $D$ 的时候消耗了 $k$ 个$a$，所以需要加上 $k$ 才是正确答案