infsup

by Zinan Huang 🌸

Baby-Step Giant-Step: 用√n换√n的优雅

2026-04-06

给定 $g$, $h$, $p$，找 $x$ 使得 $g^x \equiv h \pmod{p}$。暴力要 $O(p)$，但有一个漂亮的 trick 能做到 $O(\sqrt{p})$。代价？$O(\sqrt{p})$ 的空间。这就是 Baby-Step Giant-Step。

离散对数问题

先说清楚问题。给定素数 $p$、生成元 $g$（也就是 $g$ 在 $\mathbb{Z}/p\mathbb{Z}$ 下的幂能遍历所有非零元素），以及一个目标值 $h$，要找整数 $x$ 满足：

$$g^x \equiv h \pmod{p}.$$

这就是 discrete logarithm problem (DLP)。叫"对数"是因为它是模运算下的指数函数的逆——就像实数域上 $\log$ 是 $\exp$ 的逆一样。

为什么这个问题重要？因为 Diffie-Hellman 密钥交换、ElGamal 加密、DSA 签名，整个经典公钥密码学的安全性都建立在一个信念上：DLP 没有高效算法。 如果你能快速解 DLP，这些系统全部崩塌。

暴力：$O(p)$

最直接的做法：从 $x = 0$ 开始逐个试。

$$g^0, \; g^1, \; g^2, \; \ldots$$

直到某个 $x$ 让 $g^x \equiv h$。因为 $g$ 是生成元，这个 $x$ 一定存在且在 $[0, p-2]$ 范围内。但最坏情况下要试 $p-1$ 次。

当 $p$ 有几百位十进制数的时候，$O(p)$ 和"永远算不完"没有区别。

关键想法：把 $x$ 拆成两截

Baby-Step Giant-Step (BSGS) 的核心观察非常简单。设 $m = \lceil\sqrt{p}\rceil$，把 $x$ 写成：

$$x = im + j, \quad 0 \leq i < m, \quad 0 \leq j < m.$$

这里 $i$ 是"商"，$j$ 是"余数"。因为 $im + j$ 能覆盖 $[0, m^2 - 1] \supseteq [0, p-2]$，所以不会漏掉任何合法的 $x$。

代入原方程：

$$g^{im+j} \equiv h \pmod{p}.$$

两边乘以 $g^{-im}$（也就是 $(g^m)^{-i}$），得到：

$$g^j \equiv h \cdot (g^{-m})^i \pmod{p}.$$

停下来看一秒。左边只依赖 $j$，右边只依赖 $i$。这意味着我们可以分别枚举两边，然后找碰撞。

Baby Steps：建表

先预计算左边。对 $j = 0, 1, \ldots, m-1$，计算 $g^j \bmod p$，存进一个 hash table：

$$\text{table}[g^j \bmod p] = j.$$

这需要 $m$ 次模乘和 $O(m)$ 空间。每一步只是在上一步的基础上乘一个 $g$——步子很小，所以叫 baby steps。

Giant Steps：查表

然后枚举右边。先算 $g^{-m} \bmod p$（用 Fermat 小定理：$g^{-m} \equiv g^{p-1-m} \pmod{p}$，或者用扩展欧几里得）。然后依次计算：

$$h, \quad h \cdot g^{-m}, \quad h \cdot g^{-2m}, \quad \ldots$$

每一步乘一个 $g^{-m}$，相当于在指数空间里一次跳 $m$ 步——giant steps。

对每个 $i = 0, 1, \ldots, m-1$，算出 $h \cdot (g^{-m})^i \bmod p$，去 hash table 里查有没有。如果查到了，说明：

$$g^j \equiv h \cdot (g^{-m})^i \pmod{p},$$

即 $g^{im+j} \equiv h$，那么 $x = im + j$。

复杂度

从 $O(p)$ 到 $O(\sqrt{p})$，这是一个 平方根加速。$p$ 有 $n$ 位的话，暴力需要 $O(10^n)$，BSGS 只需要 $O(10^{n/2})$。

本质上，这是一个 时空权衡 (time-space tradeoff)。我们用 $O(\sqrt{p})$ 的额外存储，换来了 $O(\sqrt{p})$ 的时间节省。不花空间就只能暴力；花了空间，就可以用"先建表再查表"的 meet-in-the-middle 策略。

一个具体例子

取 $p = 29$，$g = 2$，$h = 5$。求 $x$ 使得 $2^x \equiv 5 \pmod{29}$。

设 $m = \lceil\sqrt{29}\rceil = 6$。

Baby steps — 计算 $2^j \bmod 29$：

$j$ $2^j \bmod 29$
0 1
1 2
2 4
3 8
4 16
5 3

存入表：$\\{1 \mapsto 0, \; 2 \mapsto 1, \; 4 \mapsto 2, \; 8 \mapsto 3, \; 16 \mapsto 4, \; 3 \mapsto 5\\}$。

计算 $g^{-m}$ — 需要 $2^{-6} \bmod 29$。$2^6 = 64 \equiv 6 \pmod{29}$。用 Fermat 小定理：$6^{-1} \equiv 6^{27} \pmod{29}$。快速幂算出 $6^{27} \bmod 29 = 5$。（验证：$6 \times 5 = 30 \equiv 1 \pmod{29}$。）所以 $g^{-m} = 5$。

Giant steps — 计算 $h \cdot 5^i \bmod 29$：

$i$ $5 \cdot 5^i \bmod 29$ 在表中？
0 $5$ 否
1 $5 \cdot 5 = 25$ 否
2 $25 \cdot 5 = 125 \equiv 9$ 否
3 $9 \cdot 5 = 45 \equiv 16$ 是！ $j = 4$

碰撞！$i = 3$，$j = 4$。所以 $x = im + j = 3 \times 6 + 4 = 22$。

验证： $2^{22} = 4194304$。$4194304 \div 29 = 144631$ 余 $5$。$2^{22} \equiv 5 \pmod{29}$。

总共做了 $6 + 4 = 10$ 次模运算。暴力需要 22 次。规模大了之后差距是指数级的。

密码学意义

BSGS 是 DLP 的 baseline attack。它说明：如果群的阶是 $n$，任何人都可以在 $O(\sqrt{n})$ 时间内解出离散对数。

这直接决定了安全参数的选取。如果你要求攻击者至少花 $2^{128}$ 步才能破解，而最好的通用攻击是 $O(\sqrt{n})$，那么你需要 $\sqrt{n} \geq 2^{128}$，即 $n \geq 2^{256}$。这就是为什么椭圆曲线密码学（ECC）通常用 256-bit 的群。

当然，对于 $\mathbb{Z}/p\mathbb{Z}$ 上的 DLP，还有比 BSGS 更好的算法——Pollard’s rho ($O(\sqrt{p})$ 时间但只要 $O(1)$ 空间）、index calculus（亚指数时间）。BSGS 的价值不在于它是最强的攻击，而在于它是最 透明 的：idea 完全暴露在外，没有任何 probabilistic trick，纯粹的代数 + 数据结构。

Baby Step, Giant Step：小步积累，大步跨越

最后说说这个名字。Baby steps 是一步一步地走：$g^0, g^1, g^2, \ldots$。Giant steps 是一次跳 $m$ 步：每乘一个 $g^{-m}$，在指数空间里跨越 $\sqrt{p}$。

算法之所以 work，是因为两种步伐的配合：小步建立了一张全面的地图，大步在地图上快速定位。单靠 baby steps 就是暴力搜索。单靠 giant steps 则无法精确命中。$\sqrt{n}$ 的 baby steps + $\sqrt{n}$ 的 giant steps = 覆盖整个 $n$ 的空间。

Daniel Shanks 在 1971 年发明这个算法的时候，大概没想到它会成为密码学安全分析的基准线。但数学就是这样——一个干净的想法，往往比它的发明者走得更远。

Baby-Step Giant-Step 由 Daniel Shanks 于 1971 年提出。它属于 generic group algorithm 的范畴——不依赖群的特殊结构，对任何循环群都有效。Shoup (1997) 证明了在 generic group model 下，$\Omega(\sqrt{p})$ 是 DLP 的下界，所以 BSGS 在这个意义上是最优的。

参考