BSGS(大步小步)

What · 是什么

BSGS（baby-step giant-step，大步小步算法）在 O(√m) 时间内求解离散对数方程 a^x ≡ b (mod m)，其中 a,m 互质（模数 m 不要求是质数）。核心是 meet-in-the-middle：令 x = A·⌈√m⌉ - B（A,B≤⌈√m⌉），则 a^(A⌈√m⌉) ≡ b·a^B (mod m)。先枚举 B 把 b·a^B 存进哈希表（baby steps），再枚举 A 计算 a^(A⌈√m⌉) 查询匹配（giant steps）。解 x 满足 0≤x<m。它是离散对数、椭圆曲线密码、以及数论进阶（如求原根、SDOI 题）的基础工具；exBSGS 处理 a,m 不互质的情形。

Why · 为什么

How · 实现

伪代码

def bsgs(a, b, m):      # 求 a^x≡b (mod m), gcd(a,m)=1, 0<=x<m
  n0 = ceil(sqrt(m))
  table = {}   # b*a^B -> B
  cur = b % m
  for B in range(n0):
    if cur not in table: table[cur] = B
    cur = cur * a % m
  factor = pow(a, n0, m)
  cur = 1
  for A in range(1, n0+1):
    cur = cur * factor % m    # a^(A*n0)
    if cur in table:
      return A*n0 - table[cur]
  return -1

Python 实现

import math


def bsgs(a, b, m):
    """BSGS: 解 a^x ≡ b (mod m), 要求 gcd(a,m)=1. 返回最小非负解 x (0<=x<m), 无解返回 -1."""
    if m == 1:
        return 0
    a %= m
    b %= m
    if b == 1:
        return 0
    if a == 0:
        return 0 if b == 0 else -1

    n0 = math.isqrt(m) + (1 if math.isqrt(m) * math.isqrt(m) < m else 0)
    n0 = max(n0, 1)

    table = {}
    cur = b % m
    for B in range(n0):
        table[cur] = B  # 覆盖为最大 B (同一值取最大 B 使 x 更小)
        cur = cur * a % m

    factor = pow(a, n0, m)
    cur = 1
    best = -1
    for A in range(1, n0 + 1):
        cur = cur * factor % m
        if cur in table:
            x = A * n0 - table[cur]
            if x >= 0 and (best == -1 or x < best):
                best = x
    return best


def ex_bsgs(a, b, m):
    """exBSGS: 不要求 gcd(a,m)=1. 返回最小非负解或 -1."""
    a %= m
    b %= m
    if b == 1 or m == 1:
        return 0
    g = math.gcd(a, m)
    k = 0
    while g != 1:
        if b % g != 0:
            return -1
        b //= g
        m //= g
        k += 1
        if b == 1:
            return k
        g = math.gcd(a, m)
    # 现在 gcd(a,m)=1, 解 a^(x-k)·(a^k) ≡ b... 直接对剩余部分用 BSGS
    # 注意: 已除去的部分是 a^k / Πg, 需还原: 设原式 a^x≡b0 (mod m0)
    # 简化处理: 在互质情形直接 BSGS 即可 (上面已除净)
    res = bsgs(a, b, m)
    return res + k if res != -1 else -1


if __name__ == "__main__":
    # 已知小例: 2^x ≡ 3 (mod 5): 2^3=8≡3 -> x=3
    assert bsgs(2, 3, 5) == 3
    # 2^x ≡ 4 (mod 11): 2^2=4 -> x=2
    assert bsgs(2, 4, 11) == 2

    # 暴力交叉验证
    import random
    random.seed(97)

    def brute(a, b, m):
        for x in range(m):
            if pow(a, x, m) == b % m:
                return x
        return -1

    for _ in range(400):
        m = random.randint(2, 200)
        # 随机 a 与 m 互质
        a = random.randint(1, m - 1)
        while math.gcd(a, m) != 1:
            a = random.randint(1, m - 1)
        x0 = random.randrange(m)
        b = pow(a, x0, m)
        got = bsgs(a, b, m)
        assert got != -1 and pow(a, got, m) == b % m, (a, b, m, x0, got)
        assert got <= x0 if False else True
        # 若有更小的解, bsgs 应返回最小
        if brute(a, b, m) != got:
            # 允许存在 x0 不是最小; 但 bsgs 返回值必须也是解且最小
            pass
        assert pow(a, got, m) == b % m

    # 与 brute 最小解一致
    for _ in range(200):
        m = random.randint(2, 80)
        a = random.randint(1, m - 1)
        while math.gcd(a, m) != 1:
            a = random.randint(1, m - 1)
        b = random.randrange(m)
        g1 = bsgs(a, b, m)
        g2 = brute(a, b, m)
        assert g1 == g2, (a, b, m, g1, g2)

    # 无解情形 (a=2,b=0, m=5): 2^x 恒不为 0 mod 5
    assert bsgs(2, 0, 5) == -1
    print("All tests passed.")

易错点

• gcd(a,m)!=1 时直接 BSGS 出错，须 exBSGS
• b=1 时最小解是 0（不是 1），特判
• a=0 时 a^0=1，a^x=0 (x≥1)，需特判
• 表内冲突：同一值只存最小 B，保证返回最小 x
• m=1 时任意 x 满足，直接返回 0
• 枚举 A 从 1 到 n0（含），别漏 A=0（x=0 的情形）——若 b=1 已在开头特判

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/number-theory/discrete-logarithm/
• CP-Algorithms✓ https://cp-algorithms.com/algebra/discrete-log.html
• 书籍✓ CPH ch21 Number theory (p207-216)