Baby-Step Giant-Step 算法

问题描述

离散对数问题是，给定 $a,b,n\in \Z^+$ ，且 $a\perp n$ . 我们希望求解最小的 $x\in [0,n)$ 满足

a^x\equiv b\pmod n

Baby-Step Giant-Step 算法

令 $S=\sqrt{n}$ ，那么 $x$ 可以表示为 $x=A\sqrt{n}-B$ 其中 $A,B\le \sqrt{n}$ . 所以原式可以写作

\begin{aligned} a^x &= b \pmod{n}\\ a^{A\sqrt{n}-B}&=b\pmod{n}\\ a^{A\sqrt{n}} &= ba^{B} \pmod{n} \end{aligned}

其中 $a,b,n$ 都是已知量，所以我们可以先 $O(\sqrt{n})$ 枚举 $B$ 计算 $ba^{B}$ 存到哈希表里，再用 $O(\sqrt{n})$ 枚举 $A$ 计算 $a^{A\sqrt{n}}$ 并在哈希表里查.

为什么需要 $a\perp n$ ？

这是因为我们需要从第三行的式子倒推回第二行式子，也就是说需要 $a^{B}\perp n$ ，即 $a\perp n$

Template Code

int solve(int a, int b, int n) {
    std::unordered_map<int, int> umap;
    int S = std::ceil(std::sqrt(n * 1.0)); // 根号 n 上取整

    int t = 1;
    for (int B = 0; B <= S; B++) {
        umap[1ll * b * t % p] = B;
        // 对于 -B 部分，如果其余数相同，我们当然保留更大的 B.
        t = 1ll * t * a % p;
    } // 枚举 ba^B 部分

    int fac = fpow(a, S, p); // 计算 a^S
    t = 1;
    int ans = (1ll << 31) - 1;
    for (int A = 0; A <= S; A++) {
        auto it = umap.find(t);
        if (it != umap.end()) {
            int val = norm(1ll * A * S - it->second, n - 1);
            ans = std::min(ans, val); // 取最小值.
        }
        t = 1ll * t * fac % p;
    } // 枚举 a^{AS} 部分

    return ans >= n ? -1 : ans;
    // 如果 ans >= n 说明循环内部没有产生更新，即没有找到解.
}

Extended Baby-Step Giant-Step 算法

ExBSGS 算法处理的问题也是类似，只不过不要求 $a,n$ 互质了.

问题描述

给定 $a,b,n\in\Z^+$ ，求解

a^x=b\pmod{n}

其中 $a,n$ 不一定互质.

大体思路是，通过 transform $a,n$ 使得 $a',n'$ 互质，把问题转化为 $(a')^x=b'\pmod{n'}$ 然后用 BSGS 算法求解.

假设 $d_1=(a,n)$ ，若 $d_1 \nmid b$ 则方程无解，否则我们可以变形为

\frac{a}{d_1}\cdot a^{x-1}=\frac{b}{d_1}\pmod{\frac{n}{d_1}}

我们的目标是让 $\frac{a}{d_1}\perp \frac{n}{d_1}$ ，这样我们就可以把 $\frac{a}{d_1}$ 通过逆元放到等式右侧. 如果 $a$ 与 $\frac{n}{d_1}$ 还是不互质，那么就再除，设 $d_2=(a,\frac{n}{d_1})$ ，则

\frac{a^2}{d_1d_2}\cdot a^{x-2}=\frac{b}{d_1d_2}\pmod{\frac{n}{d_1d_2}}

我们不断的判断下去，直到 $a\perp \frac{n}{D}$ ，令 $D=\prod_{i=1}^k d_i$ . 于是方程变成了

\frac{a^k}{D}\cdot a^{x-k}=\frac{b}{D}\pmod{\frac{n}{D}}

于是 $\frac{a^k}{D}$ 在模 $\frac{n}{D}$ 意义下有逆元，可以搬到等式的右侧. 然后使用普通 BSGS 算法求解出 $x-k$ 后再把 $k$ 加回去即可.

Template Code

int solve(int a, int b, int n) {
    a %= n;
    b %= n;
    // 特判：若 b==1 或 n==1 直接让 x=0 即可
    if (b == 1 || n == 1) return 0;

    // 快速幂函数
    auto fpow = [](int b, int p, int m) {
        int res = 1;
        for (; p; p >>= 1, b = 1ll * b * b % m)
            if (p & 1) res = 1ll * res * b % m;
        return res;
    };
    // exgcd 求逆元，因为模数 n 可能是偶数
    auto exgcd = [&](auto F, int a, int b, int &x, int &y) -> int {
        if (!b) return x = 1, y = 0, a;
        else {
            int g = F(F, b, a % b, y, x);
            y -= a / b * x;
            return g;
        }
    };
    // 取模，映射到 [0, n-1]
    auto norm = [](int val, int n) { return val %= n, val += (val < 0 ? n : 0); };
    // 用 exgcd 求解逆元
    auto inv = [norm, exgcd](int val, int m) {
        int x, y;
        int g = exgcd(exgcd, val, m, x, y);
        return g == 1 ? norm(x, m) : -1;
    };
    // 普通 Baby-Step Giant-Step 算法，处理的情况是 (a,n)=1
    // 普通 BSGS 算法流程可以参考上文
    auto bsgs = [fpow](int a, int b, int n) {
        int m = 1 + std::sqrt(n * 1.0);
        std::unordered_map<int, int> u;

        for (int i = 0, t = b % n; i < m; i++) {
            u[t] = i;
            t = 1ll * t * a % n;
        }
        int factor = fpow(a, m, n);
        int res = (1ll << 31) - 1;
        for (int i = 0, t = 1 % n; i <= m; i++) {
            auto it = u.find(t);
            if (it != u.end()) {
                int x = 1ll * i * m - it->second;
                if (x >= 0) return x;
            }
            t = 1ll * t * factor % n;
        }
        return -1;
    };

    // 计算 D 值
    // 这里其实一边计算 D 和 gcd，一边在 b,n,a 里面同时除掉 gcd.
    // 同时，这里 if(ak == b) 也同时测试了前几个 k 值
    int k = 0, ak = 1 % n;
    while (true) {
        int g = std::gcd(a, n);
        if (g == 1) break;
        if (b % g != 0) return -1;
        n /= g, b /= g;
        ak = 1ll * ak * (a / g) % n;
        k++;
        if (ak == b) return k;
        a %= n;
    }

    // 这里把 a^k/D 移项到等式右侧
    auto iv = inv(ak, n);
    if (iv == -1) return -1;
    b = 1ll * b * iv % n;

    // 调用 BSGS 算法计算解
    auto res = bsgs(a % n, b, n);
    return res == -1 ? -1 : res + k; // 记得把 k 加回去
}

例题

【模板】扩展 BSGS/exBSGS

其实上文该说的已经说完了，注意关流同步.