密码学算法 - BSGS 算法一
当你在处理离散对数问题时，发现暴力破解的方法效率太低了😩，这时候 BSGS（Baby-Step Giant-Step）算法 就像一把神奇的钥匙🔑，能帮你快速找到离散对数的解。这个算法也别戏称为“北上广深”算法。🤐
欢迎来到《密码学核心算法实战》的 BSGS 专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。
BSGS算法 🌟
BSGS（Baby-Step Giant-Step）算法是一种用于求解离散对数问题的算法。给定质数 $p$，整数 $a$ 和 $b$，我们想要找到一个整数 $x$，使得 $a^x \equiv b \pmod{p}$（其中 $a$ 与 $p$ 互质）。
BSGS算法的原理 😵
根据群中生成元的性质，我们可以知道元素 $a$ 的阶（即 $a$ 的幂等于 1 的最小正整数）是 $p-1$，然后产生一种循环的效果。因此，离散对数问题的解 $x$ 必须满足 $0 \leq x \leq p-1$。
我们考虑先求出一部分 $a$ 的幂次模 $p$ 意义下的值，将它们存起来，然后使得剩下没有求值的部分能够想个办法利用已求值直接查出来。这就让我们联想到根号。
将 $x$ 表示为 $x = im - j$，其中 $m = \lceil \sqrt{p} \rceil$，$i$ 和 $j$ 是非负整数。这样我们可以将离散对数问题转化为以下形式：
小步（Baby Step）：与计算所有 $b \cdot a^j \pmod{p}$ $(j \in [0,m))$，存入哈希表（键为值，值为 $j$）。每次都是乘 $a$，所以叫做小步。
大步（Giant Step）：计算 $a^m \pmod{p}$，遍历 $i \in [1,m]$，计算 $(a^m)^i \pmod{p}$，检查是否在哈希表中存在对应的值，如果存在，则可以得到 $x = im - j$。每次都是乘 $a^m$，所及叫做大步。
$j$ 是小步的步数，范围为 $0 \leq j < m$，因为 $j$ 是拆分后的余项，必须小于块大小 $m$ （类似除法中的余数）。当然，如果 $j \geq m$，可以通过 $i$ 来调整，本质是上是多余的。
$i$ 是大步的步数，范围为 $1 \leq i \leq m$，我们分两步证明：
先证明：所有 $x \in [0, p-1]$ 都可以表示为 $x = im - j$，其中 $i \in [1, m]$，$j \in [0, m)$。
由于 $m = \lceil \sqrt{p} \rceil$，我们有 $m^2 \geq p$。对于任意 $x \in [0, p-1]$，我们可以将其除以 $m$ 得到商 $i$ 和余数 $j$，即 $x = im + j$。由于 $x < p \leq m^2$，我们有 $i < m$ 和 $j < m$。因此，所有的 $x$ 都可以表示为 $x = im - j$。
再证明： $i$ 不用超过 $m$。
若 $i > m$，则 $x = im - j > m^2 - j \geq m^2 - (m-1) = m^2 - m + 1$。由于 $m^2 \geq p$，我们有 $x > p - m + 1$。因此，如果 $i > m$，则 $x$ 将超过 $p-1$，这与 $x \in [0, p-1]$ 矛盾。因此，$i$ 不用超过 $m$。
BSGS算法的实现 🙃
下面是 BSGS 算法的一个简单实现：
import math
def bsgs(a, b, mod):
# 前提断言：a 与 mod 必须互质，否则直接报错
assert math.gcd(a, mod) == 1, "a 与 mod 不互质，基础 BSGS 无法求解"
a = a % mod # 先取模，防止底数过大
b = b % mod # 先取模，防止结果过大
# 特殊情况：b ≡ 1 mod mod，直接返回 x=0
if b == 1:
return 0
k = math.ceil(math.sqrt(mod))
step_dict = dict()
# 小步 (Baby Step)
# 计算: b * a^q mod mod，q ∈ [0, k)
right_val = b # 初始值: b * a^0
for q in range(k):
# 只存第一次出现的q（保证q最小，从而解x最小）
if right_val not in step_dict:
step_dict[right_val] = q
right_val = right_val * a % mod
# 大步 (Giant Step)
# 计算: (a^k)^p mod mod，p ∈ [1, k]
ak = pow(a, k, mod)
left_val = 1 # 初始值: (a^k)^0
for p in range(1, k + 1):
# 用递推代替重复幂运算
left_val = left_val * ak % mod
if left_val in step_dict:
q = step_dict[left_val]
x = k * p - q
# 验证解的有效性（防止哈希碰撞或理论误差）
if pow(a, x, mod) == b:
return x
return None # 遍历结束未找到，无解
扩展BSGS算法 🥰
当 $a$ 和 $mod$ 不互质时，基础的 BSGS 算法无法直接求解。这时候我们可以使用扩展 BSGS 算法来处理这种情况。
我们把题目所给的这个式子搬出来：
我们不妨设 $gcd(a, p) = d$，如果 $d$ 不整除 $b$，则方程无解；如果 $d$ 整除 $b$，我们可以将方程两边同时除以 $d$，得到：
但是即使这样，我们也不能直接使用 BSGS 算法来求解，因为 $\frac{a}{d}$ 和 $\frac{p}{d}$ 可能仍然不互质。我们需要继续进行约简，直到 $\frac{a}{d}$ 和 $\frac{p}{d}$ 互质为止，即：
这个时候，我们再处理一下：
这样我们就得到了一个新的离散对数问题，其中底数和模数已经互质了，我们就可以使用 BSGS 算法来求解了。
扩展BSGS算法的实现 🤪
下面是这个算法的python简单实现：
def extended_bsgs(a, b, mod):
# 保存原始值（关键！用于小解验证）
orig_a = a
orig_b = b
orig_mod = mod
a = a % mod
b = b % mod
# 特殊情况：b ≡ 1 mod mod，x=0
if b == 1:
return 0
# 特殊情况：mod=1，所有 x 都满足，返回最小非负解 0
if mod == 1:
return 0
k = 0
C = 1 # 记录左边累积的系数
while True:
d = math.gcd(a, mod)
if d == 1:
break # 已经互质，停止提取
# 如果 b 不是 d 的倍数，无解
if b % d != 0:
return None
# 提取公因数（注意：a 不除 d！之前的 a//=d 是错误的）
# 正确逻辑：a 保持原值，只除 mod 和 b
b = b // d
mod = mod // d
k += 1
# 累积系数：C = C * (a//d) mod mod
C = (C * (orig_a // d)) % mod
# 现在 a（orig_a）与 mod 互质，转化方程：C * orig_a^(x-k) ≡ b (mod mod)
# 求 C 的逆元
try:
inv_C = pow(C, -1, mod)
except ValueError:
return None # 逆元不存在，理论上不会发生
B = (b * inv_C) % mod
# 调用 BSGS 时用原始 a，不是提取后的 a
y = bsgs(orig_a, B, mod)
if y is None:
return None
x = y + k
# 验证小解：x < k 的情况（用原始值验证）
for i in range(k):
if pow(orig_a, i, orig_mod) == orig_b:
return i
# 验证最终解是否满足原方程
if pow(orig_a, x, orig_mod) == orig_b:
return x
return None
SageMath 偷懒 🤓👆
有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻
有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：
from sage.all import discrete_log
# discrete_log中内置了BSGS算法，当然更加完善
r = discrete_log(b, a, mod)
# 但是需要注意：如果 a 和 mod 不互质，discrete_log 可能会抛出异常，这时候我们需要先处理一下，或者直接使用 extended_bsgs 来求解。
怎么样，是不是非常简单？🤣👉🤡
上一章：密码学算法 - Miller-Rabin素数检验 👈
下一章：密码学算法 - BSGS算法二 👈
回到开始：关于我 👈
相关链接：
密码学数学基础 - 群论基础 👈
