The site's ninth Number Theory entry, and a mirror image of one already here.
Modular Exponentiation answers "given
g, x, and p, what is gx mod p" — cheaply,
in O(log x). The discrete logarithm problem asks the reverse: given
g, h, and p, find the exponent x such that
gx ≡ h (mod p). Squaring is fast in both directions for ordinary real numbers —
if you can compute gx quickly, "undoing" it with a logarithm is just as quick.
Modular exponentiation breaks that symmetry: computing the forward direction stays cheap, but no
sub-exponential general algorithm is known for reversing it when p is large, and that
one-way gap is the entire basis of Diffie–Hellman key exchange and ElGamal encryption. Baby-step
giant-step, published by Daniel Shanks in 1971, doesn't break that gap — it's still exponential in the
number of digits of p — but it beats the obvious brute-force search
(O(p), try every exponent) by trading time for memory via one of the oldest tricks in
algorithm design: meet in the middle.
Enter a modulus p, a base g, and a target h, then step through
both phases. p = 23, g = 5, h = 8 is the standard case — 5 is a primitive root mod 23
(it generates every nonzero residue), and the algorithm finds x = 6. p = 23, g = 5,
h = 14 needs the full table: the true answer is x = 21, the largest exponent in
range, right at the edge the table has to reach — toggle "undersized m" below on this preset and watch it
report no solution even though one exists, the first pitfall below.
p = 23, g = 4, h = 5 has no solution at all: 4 only generates 11 of the 22 nonzero
residues mod 23, and 5 isn't one of them — watch the giant-step phase run to completion and correctly
report failure instead of hanging or guessing.
baby steps — table of g^j mod p, oldest to newest:
giant steps — h·g^(−jm) mod p checked against the table:
Let m = ⌈√(p − 1)⌉. Any exponent x in range [0, p − 1) can be
written as x = i·m + j for some i, j both in [0, m) — a two-digit
number in base m, essentially. Substituting into gx ≡ h gives
g^(i·m + j) ≡ h (mod p)
g^j ≡ h · g^(−i·m) (mod p)The left side depends only on j; the right side depends only on i. That
split is what makes meeting in the middle possible: precompute every left-side value once (the "baby
steps", g0, g1, …, gm−1 mod p, stored in a lookup table
keyed by value), then walk the right side ("giant steps", h·g0, h·g−m,
h·g−2m, …) checking each one against that table. The first giant step that lands on a
value already in the table gives both halves of x at once: j from the table,
i from how many giant steps it took to get there. Each phase costs at most m
work, so the total is O(m) = O(√p) instead of brute force's O(p) — for a
40-digit prime, that's the difference between roughly 20 digits of work and 10.
function modPow(base, exp, mod) {
base = ((base % mod) + mod) % mod;
let result = 1n % mod;
while (exp > 0n) {
if (exp & 1n) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1n;
}
return result;
}
function modInv(a, mod) { // extended Euclidean; works for any mod with gcd(a, mod) = 1
let [old_r, r] = [a, mod];
let [old_s, s] = [1n, 0n];
while (r !== 0n) {
const q = old_r / r;
[old_r, r] = [r, old_r - q * r];
[old_s, s] = [s, old_s - q * s];
}
return ((old_s % mod) + mod) % mod;
}
function isqrtCeil(n) { // ceil(sqrt(n)) for a non-negative BigInt n
if (n < 2n) return n;
let x = n, y = (x + 1n) / 2n;
while (y < x) { x = y; y = (x + n / x) / 2n; }
return (x * x === n) ? x : x + 1n;
}
function babyStepGiantStep(g, h, p) { // find x with g^x = h (mod p), or null
const m = isqrtCeil(p - 1n);
const table = new Map();
let e = 1n % p;
for (let j = 0n; j < m; j++) {
if (!table.has(e)) table.set(e, j); // first occurrence only
e = (e * g) % p;
}
const giantFactor = modPow(modInv(g, p), m, p); // g^(-m) mod p
let gamma = h % p;
for (let i = 0n; i < m; i++) {
if (table.has(gamma)) return i * m + table.get(gamma);
gamma = (gamma * giantFactor) % p;
}
return null; // no x in [0, m^2) works
}The interactive demo above uses an equivalent generator function that yields one event per baby or
giant step, purely to drive the step-through UI — the arithmetic is identical, including storing only
the first occurrence of each baby-step value (see Pitfalls for why that
matters) and computing the giant-step multiplier as a single modInv plus modPow
up front rather than recomputing g−im from scratch on every giant step. Verified
against 3,000 randomized trials: pick a random prime p up to 3,000, a random base
g, and a random true exponent x; compute h = gx mod p
with modular exponentiation, then confirm
babyStepGiantStep(g, h, p) returns some x′ with gx′ mod p ===
h — not necessarily the original x itself, since g may have several
valid discrete logarithms of h if its order divides p − 1 more than once, only
that the returned answer actually checks out. Zero mismatches across all 3,000. The three worked presets
above (x = 6, x = 21, and the no-solution case) were each checked directly
against a brute-force scan of every exponent from 0 to p − 2, not just against the
algorithm's own output.
Rounding m down instead of up doesn't fail loudly — it silently shrinks the range
of exponents the search can ever find, and reports "no solution" for real ones that fall outside it.
With i and j both confined to [0, m), the largest reachable
exponent is (m − 1)·m + (m − 1) = m² − 1. For p = 23, the true range needed is
[0, 21] (22 possible exponents), which requires m ≥ ⌈√22⌉ = 5; ⌊√22⌋ = 4
only reaches up to 4² − 1 = 15. Checked directly: g = 5, h = 14, p = 23 has the
true answer x = 21, and with the correctly-rounded m = 5 the algorithm finds it
in 5 giant steps — but with the floor-rounded m = 4 (toggle the checkbox above on this exact
preset), it exhausts all 4 giant steps and reports no solution, on an input that has one. The failure is
silent in the specific sense that matters most: nothing about it looks like an error, it looks exactly like
a legitimately unsolvable instance, which is exactly what the next pitfall covers.
A genuinely unsolvable instance looks identical to an undersized-m failure from the
caller's side — the algorithm can't tell you which one happened. g = 4 has order 11
mod 23 (it only generates 11 of the 22 nonzero residues), so h = 5, which isn't among them,
has no discrete logarithm base 4 at all — checked by brute force across every exponent 0 through 21, none
of them produce 5. Run the algorithm on this input (correctly-rounded m = 5, no bug involved)
and it exhausts all 5 giant steps and returns "no match," the exact same outcome shape as the previous
pitfall's bug. Both cases are "ran to completion, found nothing" — the difference between "this genuinely
has no answer" and "the search window was too small" isn't visible from the algorithm's own return value,
only from knowing independently whether h lies in the subgroup g generates. In
practice this rarely bites: most real uses (Diffie–Hellman, ElGamal) fix g as a known
generator of the full group specifically so this case can't arise, but it's worth knowing the failure
modes are indistinguishable before assuming a "no solution" result rules out a search bug.
The baby-step table must keep only the first j for a repeated value, not the
last. If g's own order is smaller than m, the sequence
g0, g1, … starts repeating before the table finishes filling —
overwriting an earlier entry with a later, larger j would hand back a valid-looking but
needlessly large x, or in the worst case, one that's actually wrong if a giant step matches
against the overwritten value using the wrong j. Storing only the first occurrence (the
reference implementation's if (!table.has(e)) guard) keeps every stored j the
smallest one that produces that value, which is also the smallest correct answer the algorithm could ever
return for a giant step landing on it.
O(√p) time and O(√p) space: the baby-step table holds up to
m ≈ √p entries, and the giant-step loop runs at most m times, each a single
lookup plus one modular multiplication. That's a real improvement over brute force's O(p)
time — for a 40-digit prime, roughly 20 digits of work instead of 40 — but it isn't free: unlike every
other entry in this category, this algorithm's cost is dominated by memory, not just time, since
the whole baby-step table has to stay resident to be checked against on every giant step. And critically,
√p is still exponential in the number of bits of p — doubling
p's bit-length roughly squares the work, not doubles it — which is exactly why
cryptographic protocols that rely on the discrete-log problem's hardness use moduli hundreds of digits
long: large enough that even this quadratic speedup over brute force stays computationally out of reach.
Faster algorithms exist for special cases (Pohlig–Hellman when p − 1 has only small prime
factors, index calculus for prime fields), but no known general algorithm beats this square-root shape by
more than a constant factor for a well-chosen, safe prime.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.