THE FOLD / CHEAT / THE EXPLOIT / THE POLLARD RHO
THE POLLARD RHO
crack a number open by walking a cycle
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Pollard’s rho algorithm finds a factor of a composite number without trial-dividing up to its square root. It iterates a simple pseudo-random map x ← x²+c (mod n) and watches for a collision modulo a hidden factor p: two iterates that agree mod p (though not mod n) reveal p as gcd(|x−y|, n). By the birthday paradox a collision mod p appears after only about √p steps — far faster than dividing by every prime. Floyd’s tortoise-and-hare finds it with no extra memory.
LIT verified live: over hundreds of semiprimes n = p·q, the returned d satisfies 1 < d < n and divides n exactly (window.__pollard). FIG no framing; the divisor is checked by exact remainder.
LIT verified live: over hundreds of semiprimes n = p·q, the returned d satisfies 1 < d < n and divides n exactly (window.__pollard). FIG no framing; the divisor is checked by exact remainder.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-exploit — pull a factor out through a crack in the number, without brute-forcing every divisor. Pollard’s rho is that crack. AVAN (AI) built the instrument: the x²+c iteration, Floyd’s cycle detection, the gcd extraction, and the divides-n check.
Credit as content: John Pollard (1975); Floyd’s cycle-finding. The weave: David names the-exploit; I walk the pseudo-random sequence with a tortoise and a hare until their gap shares a factor with n, then confirm the extracted divisor really divides n — a factor found by a cycle, not a search.
Credit as content: John Pollard (1975); Floyd’s cycle-finding. The weave: David names the-exploit; I walk the pseudo-random sequence with a tortoise and a hare until their gap shares a factor with n, then confirm the extracted divisor really divides n — a factor found by a cycle, not a search.
3 ONE DIMENSION
The map x ← x²+c (mod n) eventually cycles — a “rho” shape. Two points colliding mod a hidden factor p (not mod n) make gcd(|x−y|, n) reveal p. A collision appears after ~√p steps.
4 TWO DIMENSIONS · INTERACTIVE
Factor a semiprime; watch the iteration and the moment gcd reveals a divisor, checked to divide n.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a factor pulled from a cycle.
AVAN’s addition (the inverse-companion): find a factor by colliding modulo it, not by dividing — iterate x²+c and let the birthday paradox produce a match mod the hidden p after ~√p steps, exposed by a gcd. The inverse of ‘test every prime up to √n’ is ‘walk a pseudo-random cycle until its gap betrays a factor.’ Magenta is the √n trial division skipped; green is the ~√p cycle collision. Factoring by coincidence, made to happen.
LIT Genuine Pollard's rho factorization (John Pollard 1975; Floyd cycle detection). Verified live: over 300 semiprimes n = p·q with p,q prime in [101,2000), the tortoise-and-hare iteration of x²+c returns a divisor d with 1
FIG No framing: the x²+c iteration, Floyd's cycle detection, the gcd extraction, and the divides-n check run in-browser and agree. Honest scope: rho is a heuristic (expected ~√p steps, retried with new c on failure), verified here by confirming the returned divisor genuinely divides n — not by claiming a worst-case bound. The AVAN inverse is honest — finding a factor via a collision modulo the hidden p replaces trial division to √n; magenta is that √n scan skipped, green the ~√p cycle collision.
FIG No framing: the x²+c iteration, Floyd's cycle detection, the gcd extraction, and the divides-n check run in-browser and agree. Honest scope: rho is a heuristic (expected ~√p steps, retried with new c on failure), verified here by confirming the returned divisor genuinely divides n — not by claiming a worst-case bound. The AVAN inverse is honest — finding a factor via a collision modulo the hidden p replaces trial division to √n; magenta is that √n scan skipped, green the ~√p cycle collision.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN