漫谈 Baby-Step Giant-Step 算法

我们不妨想象一个巨大的操场，其上等距排列着从 $0$ 到 $p - 1$ 的 $p$ 个位置，起始时我们站在位置 $1$（单位元）。$x$ 从 $0$ 开始，每增加 $1$，我们就从现在的位置 $r$ 前进一次 到 $ar \bmod p$；该过程将始终进行，直到在前进 $x$ 次后，我们停在了位置 $b$ 上。最暴力的方法即为枚举，但对于大多数题目而言，$p$ 的值通常很大，在大的操场上枚举是较为困难的。

BSGS 算法可以解决这样的问题。假如现在我们向操场派出两个人，Baby-Step 和 Giant-Step，让他们帮助我们完成在操场上行走。值得注意的是，两个人的行走策略有所差异：Baby-Step 每次行动仅前进一次，但 Giant-Step 每次行动可前进多次。 我们让 Baby-Step 和 Giant-Step 分别从终点和起点出发，他们在操场上各自前进；当他们相遇的时候，我们取 Giant-Step 从起点到相遇点的前进次数和 Baby-Step 从终点到相遇点的前进次数，只需对两者作差，即得到我们从起点到终点需要前进的次数，并可以以此推导出答案。

这里，我们将总前进次数 $x$ 分为

其中，$i$ 表示 Giant-Step 的行动次数，$m$ 表示 Giant-Step 的一次行动前进多少次，$j$ 表示 Baby-Step 的前进次数。通常取 $m$ 为 $\lceil \sqrt{p} \rceil$。我们将上述式子先代入原方程中，有

在同余式两边同乘以 $a^j$，得

这个式子是算法的核心。同余式左侧 $(a^m)^i$ 显示了 Giant-Step 的行动，右侧 $b \cdot a^j$ 显示了 Baby-Step 的行动。

在继续之前，我们需要说明一个前提：以下默认 $\gcd(a, p) = 1$。在多数题目中 $p$ 为素数且 $a$ 不是 $p$ 的倍数，因此这个条件自然成立。该条件保证了 $a^j$ 在模 $p$ 下可逆，从而可以从右侧等式反推出原来的 $x$。

另外，如果 $b \equiv 1 \pmod{p}$，显然 $x = 0$ 就是最小解，因此实现时应先特判并直接返回 $0$。

下面描述具体过程。

对于 Baby-Step，起初站在终点 $b$ 上，并使用一张哈希表记录着其前进的全过程：前进 $0$ 次时，记录「前进 $0$ 次到达了 $b \cdot a^0 \bmod p$」；前进 $1$ 次时，记录「前进 $1$ 次到达了 $b \cdot a^1 \bmod p$」……Baby-Step 一直如此前进直到 $(m - 1)$ 次，将这 $m$ 对「前进次数—到达位置」的关系全部记录在了一张哈希表里。现在，这个哈希表则类似于一张地图，它记录了从终点 $b$ 出发，前进不到 $m$ 次，即 $0$ 到 $m-1$ 次能到达的所有位置。若同一个位置被多次到达，实现时应保留更大的 $j$，以保证最终得到的 $x = im - j$ 尽可能小。

下面，我们让 Giant-Step 出发，站在起点 $1$ 上。行动 $1$ 次（前进 $m$ 次）时，Giant-Step 对照哈希表以检验自己现在所处的位置 $(a^m)^1 \bmod p$ 是否位于哈希表内：如果有，则停止；如果否，则继续行动 $1$ 次。Giant-Step 将一直行动，直到第 $i$ 次行动时，其处于的位置 $(a^m)^i \bmod p$ 恰好位于哈希表内。这样，我们便知道了：Giant-Step 从起点 $1$ 出发，行动 $i$ 次（前进 $im$ 次）后到达了相遇点；Baby-Step 从终点 $b$ 出发，前进 $j$ 次后也到达了相遇点。因此，若我们从起点出发，只需前进

次即可到达终点。

由于 $m = \lceil \sqrt{p} \rceil$，任意可能的 $x < p$ 都可以写成 $x = im - j$ 的形式，其中 $1 \le i \le m$，$0 \le j < m$。因此 Giant-Step 至多行动 $m$ 次，Baby-Step 也至多记录 $m$ 条哈希表，所以算法总复杂度为 $O(\sqrt{p})$ 的时间和 $O(\sqrt{p})$ 的空间。在 MoeCTF 2025 的这道 ezBSGS 题目 中，$p$ 的值大约为 $10^{14}$，但 $\sqrt{p}$ 的值仅为 $10^7$，可以认为 BSGS 算法是容易计算的。