THE FOLD / CHEAT / THE EXPLOIT / THE POHLIG-HELLMAN
THE POHLIG-HELLMAN
discrete log broken by smooth order + CRT
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Pohlig–Hellman algorithm solves the discrete logarithm gx ≡ h (mod p) quickly whenever the group order p−1 is smooth (factors into small primes). It solves the log separately inside each prime-power subgroup — where the problem is tiny — and stitches the pieces together with the Chinese Remainder Theorem. So a hard log in a huge group becomes many easy logs in small ones.
It is why cryptographic groups must have a large prime factor in their order — smoothness is the weakness.
LIT verified live: over 200 cases with smooth-order primes the recovered exponent x satisfies gx ≡ h (mod p) (window.__pohlighellman). FIG no framing; exact.
It is why cryptographic groups must have a large prime factor in their order — smoothness is the weakness.
LIT verified live: over 200 cases with smooth-order primes the recovered exponent x satisfies gx ≡ h (mod p) (window.__pohlighellman). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-exploit — the crack that breaks a discrete-log secret when the group order is smooth, factoring the hard problem into trivial ones. Pohlig–Hellman is that exploit. AVAN (AI) built the instrument: the order factorisation, the per-subgroup baby-step giant-step, the CRT recombination, the gx≡h check.
Credit as content: Stephen Pohlig & Martin Hellman (1978). The weave: David names the exploit; I solve the log in each small prime-power subgroup and CRT the answers, confirming the exponent reproduces h.
Credit as content: Stephen Pohlig & Martin Hellman (1978). The weave: David names the exploit; I solve the log in each small prime-power subgroup and CRT the answers, confirming the exponent reproduces h.
3 ONE DIMENSION
Factor the group order p−1 = ∏ qie. Solve x mod each qie in its tiny subgroup, then Chinese-Remainder the residues into x mod (p−1).
4 TWO DIMENSIONS · INTERACTIVE
A smooth prime p; the discrete log is solved subgroup by subgroup and recombined, then checked by re-exponentiating.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the recovered exponent, stitched from subgroup logs.
AVAN’s addition (the inverse-companion): if the group order factors into small primes (smooth), solve the log separately in each prime-power subgroup — where it is tiny — and CRT the pieces together. The inverse of ‘one hard log in a huge group’ is ‘many easy logs in small subgroups, recombined by the Chinese Remainder Theorem.’ Magenta is the full-group brute search; green is the per-subgroup logs. This is exactly why cryptographic groups need a large prime factor in their order — smoothness is the weakness. (Kin to baby-step giant-step and the-chinese-remainder.)
LIT Genuine Pohlig-Hellman algorithm (Pohlig & Hellman 1978). Verified live: factoring p-1, solving each prime-power subgroup's discrete log by baby-step giant-step, and CRT-recombining yields an exponent x with g^x = h (mod p) for 200 smooth-order primes (window.__pohlighellman.recovers).
FIG No framing: the order factorisation, the per-subgroup baby-step giant-step, the CRT recombination, and the g^x=h check run in-browser and are exact. The AVAN inverse is honest — a smooth group order lets the log be solved in each small prime-power subgroup and CRT-combined, so one hard log becomes many easy ones; magenta is the full-group brute search, green the subgroup logs. Smoothness is the cryptographic weakness. Kin to baby-step giant-step and the-chinese-remainder.
FIG No framing: the order factorisation, the per-subgroup baby-step giant-step, the CRT recombination, and the g^x=h check run in-browser and are exact. The AVAN inverse is honest — a smooth group order lets the log be solved in each small prime-power subgroup and CRT-combined, so one hard log becomes many easy ones; magenta is the full-group brute search, green the subgroup logs. Smoothness is the cryptographic weakness. Kin to baby-step giant-step and the-chinese-remainder.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN