找到最小的 $x$ 使得 $a^x \equiv b \pmod{p}$。
我们不妨想象一个巨大的操场，其上等距排列着从 $1$ 到 $p$ 的 $p$ 个位置，起始时我们站在位置 $1$（单位元）。$x$ 从 $0$ 开始，每增加 $1$，我们就从现在的位置 $r$ 前进一次 到 $ar \bmod p$；该过程将始终进行，直到在前进 $x$ 次后，我们停在了位置 $b$ 上。最暴力的方法即为枚举，但对于大多数题目而言，$p$ 的值通常很大（例如在 MoeCTF 2025 的这道 ezBSGS 题目 中，$p$ 的值为 $100,000,000,000,099$），在这样大的操场上枚举是较为困难的。
BSGS 算法可以解决这样的问题。假如现在我们向操场派出两个人，Baby-Step 和 Giant-Step，让他们帮助我们完成在操场上行走。值得注意的是，两个人的行走策略有所差异：Baby-Step 每次行动仅前进一次，但 Giant-Step 每次行动可前进多次。 我们让 Baby-Step 和 Giant-Step 分别从终点和起点出发，他们在操场上各自前进；当他们相遇的时候，我们取 Giant-Step 从起点到相遇点的路程和 Baby-Step 从终点到相遇点的路程，只需对两者作差，即得到我们前进的路程，并可以以此推导出前进的次数。
这里，我们将总前进次数 $x$ 分为
$$
x = i \cdot m - j
$$
其中，$i$ 表示 Giant-Step 的行动次数，$m$ 表示 Giant-Step 的一次行动前进多少次，$j$ 表示 Baby-Step 的前进次数。通常取 $m$ 为 $\lceil \sqrt{p} \rceil$。我们将上述式子先代入原方程中，有
$$
a^{i \cdot m - j} \equiv b \pmod{p}
$$
化简并在等号两边同乘以 $a^j$，得
$$
(a^m)^i \equiv b \cdot a^j \pmod{p}
$$
这个式子是算法的核心。$\equiv$ 的前半部分显示了 Giant-Step 的行动，后半部分显示了 Baby-Step 的行动。对于 Baby-Step，ta 起初站在终点 $b$ 上，并使用一张哈希表记录着 ta 前进的全过程：前进 $0$ 次时，ta 记录「前进 $0$ 次到达了 $b \cdot a^0 \bmod p$」；前进 $1$ 次时，ta 记录「前进 $1$ 次到达了 $b \cdot a^1 \bmod p$」……Baby-Step 一直如此前进直到 $(m - 1)$ 次，ta 将这 $m$ 对 前进次数-到达位置 的关系全部记录在了一张哈希表里。现在，这个哈希表则类似于一张地图，它记录了从终点 $b$ 出发，前进 $m$ 次之内能到达的所有位置。
下面，我们让 Giant-Step 出发，ta 站在起点 $1$ 上。行动 $1$ 次（前进 $m$ 次）时，Giant-Step 对照哈希表以检验自己现在所处的位置 $(a^m)^1 \bmod p$ 是否位于哈希表内：如果有，则停止；如果否，则继续行动 $1$ 次。Giant-Step 将一直行动，直到第 $i$ 次行动时，ta 处于的位置 $(a^m)^i \bmod p$ 恰好位于哈希表内。这样，我们便知道了：Giant-Step 从起点 $1$ 出发，行动 $i$ 次（前进 $im$ 次）后到达了相遇点；Baby-Step 从终点 $b$ 出发，前进 $j$ 次后也到达了相遇点。因此，若我们从起点出发，只需前进
$$
x = i \cdot m - j \text{ (times)}
$$
即可到达终点。
传统暴力枚举算法的复杂度应为 $O(p)$，而 BSGS 算法考虑到 Baby-Step 和 Giant-Step 分别建立和查询哈希表，各自只需要行动至多 $m$ 次，取 $m = \lceil \sqrt{p} \rceil$，则总共的计算量至多为 $2 \sqrt{p}$，这将复杂度降低到了 $O(\sqrt{p})$。在 MoeCTF 2025 的这道 ezBSGS 题目 中，$p$ 的值大约为 $10^{14}$，但 $\sqrt{p}$ 的值仅为 $10^7$，可以认为 BSGS 算法是容易计算的。