Baby-Step Giant-Step (BSGS)

The core idea is beautifully simple once you see it — it's essentially a meet-in-the-middle strategy applied to the discrete logarithm problem.

The Problem

You want to find $x$ such that $g^x = h \pmod{p}$. Naively, you'd try $x = 0, 1, 2, \dots, p-1$ which takes $O(p)$ time where $p$ is the group order.

The Key Insight

Write $x = i \cdot m + j$ where $m = \lceil\sqrt{p}\rceil$ and $0 \le i, j < m$. Then:

$g^{im + j} = h$

$g^j = h \cdot (g^{-m})^i$

You've split one search over $p$ values into two searches over $\sqrt{p}$ values each.

The Two Phases

Baby steps — Precompute and store $g^j$ for $j = 0, 1, \dots, m-1$ in a hash table. These are small, incremental steps through the group.

Giant steps — Compute $h \cdot (g^{-m})^i$ for $i = 0, 1, 2, \dots$ and check if it's in your table. Each iteration jumps by $m$ positions — hence "giant" steps.

When you find a collision, you've got $g^j = h \cdot g^{-im}$, so $h = g^{im+j}$ and $x = im + j$.

Walkthrough: $5^x \equiv 20 \pmod{53}$

Here $g = 5$, $h = 20$, and the group order is $p = 52$ (since $(\mathbb{Z}/53\mathbb{Z})^*$ has order $53 - 1 = 52$).

Setup. Compute $m = \lceil\sqrt{52}\rceil = 8$.

Baby steps — build a table of $g^j \bmod 53$ for $j = 0, \dots, 7$:

Store as a lookup: $\{1 \mapsto 0,\; 5 \mapsto 1,\; 25 \mapsto 2,\; 19 \mapsto 3,\; 42 \mapsto 4,\; 51 \mapsto 5,\; 43 \mapsto 6,\; 3 \mapsto 7\}$.

Giant steps — we need $g^{-m} = 5^{-8} \bmod 53$. Since $5^8 \equiv 15 \pmod{53}$, we find $15^{-1} \equiv 46 \pmod{53}$ (verify: $15 \cdot 46 = 690 = 13 \cdot 53 + 1$). Now compute $h \cdot (g^{-m})^i = 20 \cdot 46^i \bmod 53$:

Result. $x = i \cdot m + j = 1 \cdot 8 + 3 = 11$.

Verify: $5^{11} = 5^8 \cdot 5^3 = 15 \cdot 19 = 285 = 5 \cdot 53 + 20 \equiv 20 \pmod{53}$. Correct.

We checked just $8 + 1 = 9$ values instead of scanning all 52. With larger groups, this savings becomes dramatic.

Why It Works Mathematically

Every integer $x \in [0, p)$ can be uniquely decomposed as $x = im + j$ with $0 \le j < m$ and $0 \le i < m$. So the baby steps cover all possible "remainders mod $m$" and the giant steps cover all possible "quotients by $m$." The two sets are guaranteed to collide at the right answer.

Complexity

• Time: $O(\sqrt{p})$ — at most $\sqrt{p}$ baby steps + $\sqrt{p}$ giant steps
• Space: $O(\sqrt{p})$ — storing the baby-step table

This is optimal for generic group algorithms (by Shoup's lower bound), meaning you can't do better without exploiting special group structure.