Pohlig-Hellman — solving the discrete log when the group order is smooth

Pohlig-Hellman solves g^x = h by splitting the discrete log into one small problem per prime-power factor of the group order and recombining the pieces with CRT — it is fast precisely when that order is *smooth* (only small prime factors).

The signal that gives it away

- You can compute the group order n (or the relevant subgroup order) and, when you factor it, every prime factor p_i is modest — this is the "modulus is prime but p-1 is smooth" trap on classic multiplicative-group DH/ElGamal, and the analogous trap for an elliptic-curve order. - On a curve: E.order() factors into small pieces (check with factorint/factor — this is step one of any DLP triage, before reaching for anything heavier). - On DH parameters: p is prime but p-1 factors smoothly — audit this first, it is "the whole game" for any DH-shaped challenge. - A live oracle that leaks something about a *static* secret exponent when queried repeatedly is the same signal in disguise: sending crafted low-order elements and reading back partial information is Pohlig-Hellman driven through an oracle instead of computed offline from a known order. - Distinguish it from a *composite modulus* that is itself factorable (e.g. an RSA-shaped n = p*q used as a DH modulus) — there the unlock is factoring the modulus, not the group order; don't reach for Pohlig-Hellman when factoring n directly is the actual shortcut.

How to exploit

1. Factor the group order: n = ∏ p_i^{e_i}. 2. For each prime-power factor p_i^{e_i}: project both generator and target into that subgroup, g_i = g^(n / p_i^{e_i}), h_i = h^(n / p_i^{e_i}), and solve the now-tiny discrete log g_i^{x_i} = h_i to get x mod p_i^{e_i}. This inner solve is Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log (or Pollard rho) — feasible as long as p_i itself stays in the roughly 2^40–2^48 range that BSGS tolerates in memory. 3. Recombine every x_i = x mod p_i^{e_i} into x mod n with Chinese Remainder Theorem — recombining residues across coprime moduli. 4. Complexity is sum_i e_i (log n + sqrt(p_i)) — the running time is governed entirely by the *largest* prime factor of n, not by n itself. This is why a 2048-bit smooth order can still be trivial while a 60-bit prime order is not. 5. In practice you don't hand-roll it: Sage's discrete_log(h, g, ord=n) (or E.discrete_log() / .weil_pairing tooling for curves) applies Pohlig-Hellman automatically once you hand it the correct order. Always verify with g**x == h (or k*P == Q on a curve) afterward — a silent wrong-branch CRT bug is easy to miss otherwise. 6. Oracle variant (no offline order factorization needed): craft an element h_i of small order q_i (e.g. g0^((p-1)/q_i) for a chosen small q_i), send it to whatever oracle exponentiates by the static secret, and read the residue secret mod q_i off the response. Repeat for enough coprime q_i that their product exceeds the secret's range, then CRT-recombine exactly as in step 3 — this is the same algorithm, just with the "small subgroup" chosen by the attacker instead of found by factoring a fixed order. See DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order and DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle for the oracle mechanics. 7. On elliptic curves, PH is one branch of a larger triage, not a first resort: check curve order for smoothness only after ruling out the anomalous case (n == p, Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time, polynomial time — linear in log p — via the p-adic/Smart lift, far faster than generic ECDLP) and the singular case (zero discriminant, Singular Curve Attack — the zero-discriminant signal that collapses ECDLP to a field problem, reduces the curve group to F_p^* or F_{p^2}^* — often smooth enough that Pohlig-Hellman finishes the job *after* that reduction).

What does NOT work

- Treating it as a magic bullet when only part of the order is smooth. If n = (huge prime) * (smooth cofactor), Pohlig-Hellman only recovers x mod (smooth cofactor) for free. That is a partial answer, not a solved challenge — the remaining large prime factor needs Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure (large prime field, no special structure) or a generic square-root method, and if it's a properly-sized prime with no structure, it may simply not be solvable in reasonable time — that's the entire point of using a safe prime for DH/ElGamal in the first place. - Running it against a composite modulus expecting it to factor the modulus. Pohlig-Hellman factors the *group order*, not the modulus; if the modulus itself looks RSA-shaped, that's a factoring problem (Integer Factorization Methodology — which factoring attack to try, in what order), a different attack even though the surface symptom ("this number factors nicely") looks similar. - Skipping the subgroup-order check and running BSGS against the full `p-1` or full curve order. If you don't first factor the order and dispatch per prime power, you pay the cost of the *largest* factor for the *whole* problem instead of per-piece — the entire speed advantage disappears if you don't actually split the work. - Applying it where the anomalous or singular special cases apply instead. If curve order equals the field characteristic, Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time runs in polynomial time (linear in log p) and is strictly better than any generic method; running Pohlig-Hellman there works in principle (order is 1, trivially "smooth") but signals you missed the faster, more specific path. Conversely, if the order is neither anomalous, singular, nor smooth, Pohlig-Hellman gives no leverage at all — that large-prime-order case is exactly what makes standard ECC curves hard, and it means the intended vulnerability is elsewhere (leaked bits, nonce reuse, side channel), not the discrete log itself.

Related

Discrete Logarithm — the factorization of the group order picks your algorithm Baby-Step Giant-Step — the generic meet-in-the-middle solver for a mid-sized discrete log Chinese Remainder Theorem — recombining residues across coprime moduli Index Calculus — sub-exponential DLP attack for large prime fields with no smooth structure Smooth Numbers — the concept behind why Pollard p-1, Pohlig-Hellman, and index calculus work (and when they don't) DH Small-Subgroup Attack — confining the secret to a tiny subgroup to leak it mod that order DH Static-Key Reuse — turning a persistent secret exponent into a leaking oracle Key-Exchange Methodology — triage any DH/ECDH challenge before reaching for heavy DLP machinery Elliptic Curve Discrete Logarithm Problem — the curve order's factorization picks your attack Smart Attack — the anomalous-curve signal that turns ECDLP into polynomial time Singular Curve Attack — the zero-discriminant signal that collapses ECDLP to a field problem Diffie-Hellman Fundamentals — what to audit first in any DH challenge