Lab 08 — Discrete Logarithm: Baby-Step Giant-Step

Goal

Solve g^x ≡ h (mod p) in O(√p) time and space with Shanks’ baby-step giant-step (1971), and know when Pollard’s rho or Pohlig-Hellman is the right tool instead.

Background

The discrete logarithm problem (DLP): given g, h, p, find x with g^x ≡ h (mod p). The forward direction (modular exponentiation) costs O(log x); no known classical algorithm inverts it in polynomial time. That asymmetry is the security basis of Diffie-Hellman key exchange and DSA.

Shanks (1971), meet-in-the-middle: let m = ⌈√p⌉. Any candidate x decomposes as x = i·m + j with 0 ≤ j < m, 0 ≤ i ≤ m. Precompute baby steps g^j into a hash table; then take giant steps γ = h·(g^−m)^i and probe the table — a hit at (i, j) means x = i·m + j. The classical inverse-free twin uses x = i·m − j: baby steps h·g^j into the table, giant probes (g^m)^i. Either way: two O(√p) halves replace one O(p) scan.

Pollard’s rho for logarithms: same O(√p) expected time, O(1) space — pseudorandom walk over group elements tracked as g^a·h^b, cycle found via Floyd/Brent, then solve a linear congruence mod p−1. The answer when the BSGS table doesn’t fit in RAM.

Pohlig-Hellman: if p−1 is smooth (only small prime factors), solve the DLP independently in each prime-order subgroup — each at O(√q) by BSGS or rho — and recombine with CRT (cross-ref phase-12 lab-07). Total cost is dominated by the largest prime factor of the group order.

Interview Context

  • Cryptography / security engineering: standard (CTFs, protocol audits, parameter reviews)
  • ICPC / Codeforces: occasional — BSGS is the intended trick behind “find k with a^k ≡ b” subproblems
  • Blockchain / applied-crypto roles: expected vocabulary (ECDLP hardness is why keys are 256 bits)
  • Quant: rare
  • Standard FAANG: zero — this does not appear on LeetCode

When to Skip This Topic

Skip if any of these are true:

  • You aren’t targeting cryptography, security, or ICPC roles
  • Modular exponentiation and inverses (phase-07 labs 01–02) aren’t automatic yet
  • Your pipeline is standard FAANG loops only

If you skip, still learn one sentence: “DLP is easy forward, believed hard backward — that gap is Diffie-Hellman.”

Problem Statement

Given a prime p ≤ 10^18, a generator g of F_p*, and a target h with 1 ≤ h < p, find the smallest x ≥ 0 such that

g^x ≡ h (mod p)

or report none. (None is only possible when g is not actually a full generator and h lies outside the subgroup ⟨g⟩.)

Constraints

  • p prime, p ≤ 10^18 in principle; the hash table has m = ⌈√p⌉ entries, so memory binds first
  • Realistic single-machine range: p ≤ 10^12 in Python (m ≈ 10^6 dict entries), ~10^14–10^16 in C++
  • 1 ≤ g, h < p
  • Wall-clock: O(√p) modular multiplications

Clarifying Questions

  1. Is p guaranteed prime? (Yes — composite modulus changes the group structure; see follow-ups.)
  2. Is g guaranteed to generate all of F_p*? (Assume yes; if not, a solution may not exist — return None.)
  3. Smallest x or any x? (Smallest non-negative; solutions are unique mod ord(g).)
  4. How big is p really? (Sets BSGS vs Pollard rho — memory is the deciding constraint, not time.)

Examples

Solve 3^x ≡ 13 (mod 17). m = ⌈√17⌉ = 5.

Baby-step table, table[g^j] = j:

j:    0  1  2   3   4
3^j:  1  3  9  10  13

Giant multiplier: 3^5 = 243 ≡ 5 (mod 17), and 5^−1 ≡ 7 (mod 17), so g^−m ≡ 7.

i=0: γ = 13 → in table at j=4 → x = 0·5 + 4 = 4

Check: 3^4 = 81 = 4·17 + 13 ✓

Second target h = 5, forcing a real giant step:

i=0: γ = 5        → miss
i=1: γ = 5·7 ≡ 1  → in table at j=0 → x = 1·5 + 0 = 5

Check: 3^5 = 243 ≡ 5 (mod 17) ✓

Brute Force

Multiply an accumulator by g up to p−1 times, comparing against h. For p near 10^9: ~10^9 modmuls — seconds-to-minutes in C++, dead in Python. For p = 10^18: dead everywhere.

Brute Force Complexity

  • Time: O(p)
  • Space: O(1)

Optimization Path

  1. Set m = ⌈√p⌉; every x < p−1 writes uniquely as x = i·m + j with 0 ≤ j < m.
  2. Baby steps: insert g^j → j for j = 0..m−1, keeping the smallest j per value.
  3. Compute the giant multiplier g^−m ≡ g^(m·(p−2)) (mod p) by Fermat’s little theorem.
  4. Giant steps: γ = h; for i = 0..m, probe γ in the table — hit means return i·m + j; else γ ← γ·g^−m.
  5. Meet-in-the-middle: O(√p) inserts + O(√p) probes replaces the O(p) scan.

Final Expected Approach

import math

def bsgs(g, h, p):
    g %= p
    h %= p
    if h == 1:
        return 0
    m = math.isqrt(p) + 1
    table = {}
    e = 1
    for j in range(m):
        if e not in table:
            table[e] = j
        e = e * g % p
    giant = pow(g, m * (p - 2), p)
    gamma = h
    for i in range(m + 1):
        if gamma in table:
            return i * m + table[gamma]
        gamma = gamma * giant % p
    return None

Storing the smallest j per value and scanning i upward guarantees the returned x is minimal — even when ord(g) < m and baby values collide. The inverse-free twin (baby steps h·g^j, giant probes (g^m)^i, answer i·m − j) is equally standard; it must store the largest j for minimality and needs the explicit h = 1 → 0 case.

Data Structures

  • Hash table of size m = ⌈√p⌉ mapping group element → smallest baby exponent
  • Two scalar accumulators; nothing else

Correctness Argument

  • Coverage: i ≤ m, j < m spans all x ≤ m² + m − 1, and m² > p > ord(g), so every candidate log is reachable.
  • Hit ⟺ solution: γ_i = h·g^(−i·m) ≡ g^j ⟺ g^(i·m + j) ≡ h.
  • Minimality: let x₀ = i₀·m + j₀ be the least solution. A hit at i < i₀ would yield a solution < x₀ — impossible. At i = i₀, the stored (smallest) j with g^j = γ is exactly j₀, else a smaller solution would exist.
  • No solution → all m+1 probes miss → None.

Complexity

  • Time: O(√p) expected (hash operations amortized O(1))
  • Space: O(√p)

Implementation Requirements

  • math.isqrt(p) + 1, never int(p ** 0.5) — float sqrt is wrong near 10^18
  • Reduce g, h mod p up front; reject h ≡ 0
  • Insert baby steps with if e not in table to keep the smallest j
  • Use three-argument pow(base, exp, mod) throughout
  • Bound the giant loop at m+1 iterations and return None cleanly

Tests

  • bsgs(3, 13, 17) = 4 and bsgs(3, 5, 17) = 5 (the hand examples)
  • bsgs(g, 1, p) = 0 for any g
  • Round-trip: random x < p−1, h = pow(g, x, p); assert pow(g, bsgs(g, h, p), p) == h and result ≤ x
  • Exhaustive cross-check vs the O(p) scan for all h, p < 10^3 (smallest x must match exactly)
  • Non-generator g of small order, h ∉ ⟨g⟩ → None
  • Performance: p ≈ 10^12 prime answers in a few seconds (m ≈ 10^6)

Follow-up Questions

  • The table is O(√p) — what if it doesn’t fit in RAM? → Pollard’s rho for logs: pseudorandom walk over elements written as g^a·h^b, Floyd/Brent cycle detection, then solve a·x ≡ b (mod p−1). Same O(√p) expected time, O(1) space. Memory kills BSGS long before time does: p = 10^18 means 10^9 table entries — tens of GB.
  • p−1 factors into small primes — can you beat √p? → Pohlig-Hellman: solve in each prime-power subgroup at O(√q) each, stitch with CRT. Cost tracks the largest prime factor of the order — which is exactly why DH/DSA standards mandate groups of (near-)prime order.
  • g isn’t a generator, or the modulus isn’t prime? → Work inside ⟨g⟩: replace p−1 with ord(g) and set m = ⌈√ord(g)⌉; if h ∉ ⟨g⟩ there is no solution. For composite n, CRT-split into prime-power moduli and solve each piece.
  • Is O(√p) optimal? → Not in F_p*: index calculus is subexponential (L_p[1/3]), which is why DH primes must be 2048+ bits. It does not transfer to elliptic-curve groups, where √-time generic attacks remain the best known — the reason 256-bit ECC matches ~3072-bit RSA/DH.
  • LeetCode-adjacent framing? → It almost never appears there. What transfers is the shape: meet-in-the-middle, “split the exponent, trade √n memory for √n time” — the same instinct as splitting subset-sum search spaces in half.
  • Quantum computers? → Shor solves DLP (mod-p and elliptic-curve) in polynomial time; hence the migration to lattice-based post-quantum schemes.

Product Extension

  • CTF/security-audit tooling: recover keys from weak or undersized DH parameters
  • Parameter linters: reject groups with smooth order (Pohlig-Hellman-weak) before deployment
  • Small-subgroup confinement attack validation in protocol test harnesses
  • Distributed log-cracking via Pollard rho + distinguished points (how real DLP records are set)

Language/Runtime Follow-ups

  • Python: built-in pow and math.isqrt do the heavy lifting; a dict of 10^6–10^7 entries is fine, 10^8 is not.
  • C++: 64-bit modmul needs unsigned __int128; unordered_map with reserve, or sort-plus-binary-search over a baby array to halve memory.
  • Java: BigInteger.modPow is correct but slow; boxed HashMap<Long,Integer> overhead is real at 10^7 entries.
  • Rust: u128 intermediates; HashMap::with_capacity to avoid rehashing.

Common Bugs

  1. Float square root: int(p ** 0.5) is off by one for large p; solutions near p−1 silently vanish.
  2. Overwriting baby entries: keeping the last j instead of the smallest returns a valid but non-minimal x when ord(g) < m.
  3. Loop bounds shaved: j must cover 0..m−1 and i must reach m; either off-by-one loses logs near p−1.
  4. Missing h = 1: the i·m − j variant never probes x = 0 and returns p−1 instead.
  5. Wrong inverse: pow(g, p−2, p) needs p prime; composite modulus requires extended Euclid with gcd(g, n) = 1.
  6. Unreduced inputs: h ≥ p makes every probe miss — returns None with no error.

Debugging Strategy

  • Test the property, not the value: pow(g, bsgs(g, h, p), p) == h for random round-trips
  • Exhaustive diff against the O(p) brute force for p < 10^4 — catches minimality bugs
  • Print (i, γ) probe traces for p = 17 and diff against the hand table above
  • Feed a deliberate non-generator and confirm None, not garbage

Mastery Criteria

  • Implement bsgs (minimal x, h = 1, None case) bug-free in ≤ 30 min
  • Solve a mod-17 instance fully by hand in ≤ 5 min
  • Recite the BSGS / Pollard rho / Pohlig-Hellman trade-off table (time, space, order-smoothness) from memory
  • Explain in two sentences why index calculus makes ECC keys shorter than DH keys
  • Recognize meet-in-the-middle exponent splits in non-crypto problems