Baby-Step Giant-Step & Pohlig-Hellman

Intuition, Vocabulary and Foundations

A discrete logarithm reverses repeated group multiplication. If $g$ generates a cyclic subgroup of order $n$, solving $g^x=h$ means finding the position of $h$ on the cycle $1,g,g^2,\ldots,g^{n-1}$. Modulo $29$, for example, $2^{11}\equiv18$, so the logarithm of $18$ to base $2$ is $11$.

Linear search may inspect all $n$ exponents. Baby-step giant-step writes $x=im+j$, with $m=\lceil\sqrt n\rceil$, and searches for a collision $h(g^{-m})^i=g^j$. Pohlig–Hellman exploits a factorization $n=\prod q_i^{e_i}$: it finds $x$ modulo every prime power and reconstructs $x\bmod n$ with CRT.

BSGS splits one search into two dimensions of size about $\sqrt n$. Pohlig–Hellman goes further when the exact order is smooth: project into small prime-order problems, recover exponent digits, and combine the prime-power residues with CRT.

Concept	Example	Boundary or non-example	Question answered
Cyclic subgroup	$\langle2\rangle$ modulo $29$ has order $28$	A target outside $\langle g\rangle$ has no log to base $g$	Which elements are reachable?
Collision	$h(g^{-m})^i=g^j$ gives $x\equiv im+j\pmod n$	Equality in another group proves nothing	How does BSGS recover an exponent?
Smooth order	$28=2^2\cdot7$	An order with one huge prime factor is not smooth	Is Pohlig–Hellman advantageous?
Prime-power residue	Residues modulo $4$ and $7$ determine one residue modulo $28$	Ordinary CRT does not directly merge non-coprime moduli	What does each projection recover?
Exact order	$g^n=1$ and $g^{n/q}\ne1$ for each prime $q\mid n$	A mere multiple of the order loses uniqueness	Modulo what value is the log unique?

Step-by-Step Derivations and Algorithms

For BSGS, store $g^j$ for $0\le j\lt m$. Starting with $\gamma=h$, multiply by $g^{-m}$ after every lookup. At iteration $i$, the invariant is $\gamma=h(g^{-m})^i$. A table match $\gamma=g^j$ yields $h=g^{im+j}$; verify the candidate before returning it.

For Pohlig–Hellman, factor $n=\prod q^e$ and write $x=d_0+d_1q+\cdots+d_{e-1}q^{e-1}$. If $x_k=\sum_{j=0}^{k-1}d_jq^j$ is known, then

$$c_k=\left(hg^{-x_k}\right)^{n/q^{k+1}}=\left(g^{n/q}\right)^{d_k}.$$

The base $g^{n/q}$ has order $q$, so a small discrete-log call recovers digit $d_k$. The completed residues modulo the distinct $q^e$ factors are pairwise coprime and CRT reconstructs the unique answer modulo $n$.

Baby-Step Giant-Step & Pohlig-Hellman algorithm map

flowchart TD
    A[Validate exact order and membership] --> B{Factorization available?}
    B -->|No| C[Run BSGS in order n]
    B -->|Yes| D[Split n into prime powers]
    D --> E[Recover base-q digits]
    E --> F[Combine residues with CRT]
    C --> G[Verify exponent]
    F --> G
    G --> H[Return log or no solution]

BSGS maintains $\gamma=hg^{-im}$ and uses $O(\sqrt n)$ group operations and stored elements. Pohlig–Hellman preserves the already recovered low-order digits of $x$ and requires about $O(\sum_i e_i\sqrt{q_i})$ generic subgroup work, so its cost is governed chiefly by the largest prime factor.

Implementation, Complexity and Engineering

The reference implementation works in the multiplicative group modulo a prime. It proves that the supplied order is exact, checks target membership before allocating a table, returns None for a missing solution, validates the complete factorization, and verifies the final exponent. For large inputs, estimate the BSGS table first: an $80$-bit prime-order subgroup would require roughly $2^{40}$ entries.

from math import isqrt


def is_prime(n):
    if not isinstance(n, int) or isinstance(n, bool) or n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    d = 3
    while d <= isqrt(n):
        if n % d == 0:
            return False
        d += 2
    return True


def factorize(n):
    if not isinstance(n, int) or isinstance(n, bool) or n <= 0:
        raise ValueError("order must be positive")
    result, d = {}, 2
    while d * d <= n:
        while n % d == 0:
            result[d] = result.get(d, 0) + 1
            n //= d
        d = 3 if d == 2 else d + 2
    if n > 1:
        result[n] = result.get(n, 0) + 1
    return result


def bsgs(g, h, p, order):
    if order <= 0:
        raise ValueError("order must be positive")
    g, h = g % p, h % p
    if g == 0:
        raise ValueError("g must be invertible")
    m = isqrt(order)
    if m * m < order:
        m += 1
    table, value = {}, 1
    for j in range(m):
        table.setdefault(value, j)
        value = value * g % p
    factor = pow(pow(g, m, p), -1, p)
    gamma = h
    for i in range(m + 1):
        if gamma in table:
            candidate = i * m + table[gamma]
            if candidate < order and pow(g, candidate, p) == h:
                return candidate
        gamma = gamma * factor % p
    return None


def crt(residues, moduli):
    product = 1
    for modulus in moduli:
        product *= modulus
    answer = 0
    for residue, modulus in zip(residues, moduli):
        part = product // modulus
        answer += residue * part * pow(part, -1, modulus)
    return answer % product


def validate(g, h, p, order, factors):
    if not is_prime(p) or (p - 1) % order:
        raise ValueError("invalid prime or order")
    product = 1
    for q, exponent in factors.items():
        if not is_prime(q) or exponent <= 0:
            raise ValueError("invalid factorization")
        product *= q ** exponent
    if product != order:
        raise ValueError("factorization does not match order")
    g, h = g % p, h % p
    if g == 0 or h == 0 or pow(g, order, p) != 1:
        raise ValueError("elements or order are invalid")
    for q in factors:
        if pow(g, order // q, p) == 1:
            raise ValueError("order is not exact")
    return g, h, pow(h, order, p) == 1


def pohlig_hellman(g, h, p, order, factors=None):
    factors = factorize(order) if factors is None else dict(factors)
    g, h, member = validate(g, h, p, order, factors)
    if not member:
        return None
    residues, moduli = [], []
    for q, exponent in sorted(factors.items()):
        partial = 0
        base = pow(g, order // q, p)
        for position in range(exponent):
            correction = h * pow(pow(g, partial, p), -1, p) % p
            projected = pow(correction, order // q ** (position + 1), p)
            digit = bsgs(base, projected, p, q)
            if digit is None:
                return None
            partial += digit * q ** position
        modulus = q ** exponent
        residues.append(partial % modulus)
        moduli.append(modulus)
    answer = crt(residues, moduli)
    if pow(g, answer, p) != h:
        raise ArithmeticError("certificate failed")
    return answer


p, g, order, factors = 29, 2, 28, {2: 2, 7: 1}
for exponent in range(order):
    target = pow(g, exponent, p)
    assert bsgs(g, target, p, order) == exponent
    assert pohlig_hellman(g, target, p, order, factors) == exponent

assert pohlig_hellman(2, 18, 29, 28, factors) == 11
assert bsgs(4, 2, 29, 14) is None
assert pohlig_hellman(4, 2, 29, 14, {2: 1, 7: 1}) is None

for args in ((2, 18, 21, 12, {2: 2, 3: 1}),
             (4, 16, 29, 28, factors),
             (2, 18, 29, 28, {2: 2, 5: 1})):
    try:
        pohlig_hellman(*args)
    except ValueError:
        pass
    else:
        raise AssertionError("invalid domain was accepted")

print("all tests passed")

Method	Time and memory	Failure mode	Mitigation
Linear search	$O(n)$ time, $O(1)$ memory	Too slow beyond tiny groups	Use only as a testing oracle
BSGS	$O(\sqrt n)$ time and memory	Table exceeds memory	Estimate entries first or use a rho method
Pohlig–Hellman	About $O(\sum e_i\sqrt{q_i})$ subgroup work	One large prime factor dominates	Measure security by the largest prime-order component
Supplied order	Avoids order discovery	A multiple of the true order breaks uniqueness	Test $g^{n/q}\ne1$ for every prime $q\mid n$
Membership check	One exponentiation $h^n$	Unsafe if the base order is not exact	Validate exact order first
CRT	Efficient across prime-power factors	Ordinary CRT needs coprime moduli	Combine distinct prime powers only

Applications, Case Studies and Exercises

For $p=29$, $g=2$, and $h=18$, BSGS with $m=6$ finds $x=11$. Pohlig–Hellman uses $28=4\cdot7$, recovers $x\equiv3\pmod4$ and $x\equiv4\pmod7$, and CRT returns $11\pmod{28}$. In security engineering, this structure explains why a large total group order is insufficient: if it is smooth, the discrete logarithm decomposes into inexpensive problems.

Practice

Apply Baby-Step Giant-Step & Pohlig-Hellman

Case study 1. Build the BSGS table for $p=29$, $g=2$, $h=18$, and $m=6$; trace giant steps to the collision and verify $2^{11}\equiv18$. Then derive the residues modulo $4$ and $7$. Success means CRT returns $11$.

Case study 2. Compare groups of orders $2^{10}3^6$ and $2q$, where $q$ is a large prime of comparable bit length. Estimate the largest subgroup table and list required membership checks. Success means the security comparison is based on the largest prime factor.

Exercises. Prove the BSGS collision equation; derive one Pohlig–Hellman digit step; exhaustively compare both solvers with direct search in small fields; reject wrong orders, incomplete factorizations, and outside-subgroup targets; add a table-size limit and operation counters.

Use direct search only as a tiny oracle, BSGS for moderate generic orders when square-root memory is acceptable, and Pohlig–Hellman for known smooth orders. Never confuse a multiple of the base order with its exact order or assess cryptographic strength from total group size alone; subgroup validation and the largest prime factor determine the real boundary.

Cookie Consent