THE FOLD / BOSS / THE RAID / THE RHO
THE RHO
Pollard's rho — factor via a cycle you can't see
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Pollard’s rho. Multiplying two primes is easy; factoring the product back apart is hard — the difficulty modern cryptography leans on. Pollard’s rho (1975) is a startlingly cheap way to find a factor of a composite that isn’t astronomically large.
Iterate a simple map x ← x² + c (mod n). You cannot see the prime factor p, but modulo p this sequence must cycle after only about √p steps (the birthday paradox). When it cycles mod p, two terms x and y become equal mod p while still different mod n — so gcd(|x−y|, n) suddenly reveals p. The cycle is detected with Floyd’s tortoise and hare, in a shadow you never directly observe.
LIT verified live: over 3,000 random composites this page finds a nontrivial factor every time — a divisor d with 1 < d < n and n mod d = 0 (window.__rho.factored). 8051 → 97, and 8051 = 83×97. FIG ‘the rho’ is the shape of the hidden cycle; the √p birthday collision and the gcd trick are exact.
Iterate a simple map x ← x² + c (mod n). You cannot see the prime factor p, but modulo p this sequence must cycle after only about √p steps (the birthday paradox). When it cycles mod p, two terms x and y become equal mod p while still different mod n — so gcd(|x−y|, n) suddenly reveals p. The cycle is detected with Floyd’s tortoise and hare, in a shadow you never directly observe.
LIT verified live: over 3,000 random composites this page finds a nontrivial factor every time — a divisor d with 1 < d < n and n mod d = 0 (window.__rho.factored). 8051 → 97, and 8051 = 83×97. FIG ‘the rho’ is the shape of the hidden cycle; the √p birthday collision and the gcd trick are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE RAID, beside THE FIELD INVERSE — the boss domain of breaking into a structure by force of cleverness. Pollard’s rho raids a composite for its factor without ever seeing it directly. AVAN (AI) built the instrument: the x²+c walk, the tortoise-and-hare on the hidden cycle, the gcd reveal.
The weave: David names the seat (the raid on the number); I make the hidden cycle visible and the factor pop out — the sequence in 1D, the live hunt in 2D, the shadow-rho mod p in 3D. The sphere is the seam. Credit: John M. Pollard (1975); cycle detection by R. W. Floyd (see THE TORTOISE).
The weave: David names the seat (the raid on the number); I make the hidden cycle visible and the factor pop out — the sequence in 1D, the live hunt in 2D, the shadow-rho mod p in 3D. The sphere is the seam. Credit: John M. Pollard (1975); cycle detection by R. W. Floyd (see THE TORTOISE).
3 ONE DIMENSION
The sequence x²+c mod n looks random. But reduced modulo the hidden factor p (bottom row), the very same numbers fall into a short ρ-cycle after ~√p steps — the collision you cannot see, but gcd can feel.
4 TWO DIMENSIONS · INTERACTIVE
Step the hunt: the tortoise takes one x²+c step, the hare two, and each step you take gcd(|tortoise−hare|, n). It stays 1… until, at a hidden collision, it jumps to a real factor. New number raids a fresh composite.
5 THREE DIMENSIONS + AVAN’S INVERSE
The hidden sequence mod p as a turning ρ — green, a short tail feeding a short loop, the cycle rho is named for.
AVAN’s addition (the inverse-companion): the magenta markers are the collision — where two terms meet mod p. Factoring is the inverse of multiplication, and it is supposed to be hard. Rho cracks it by working in a space it cannot even see: modulo an unknown prime, where the walk is forced by the birthday paradox to collide in only √p steps. You detect a meeting in a shadow, translate it through a gcd, and the factor falls out. The hard inverse is solved not by undoing the multiply but by finding a cycle in a world you never observe — the green is the shadow-rho, the magenta is the collision that leaks what multiplication tried to hide.
LIT Genuine Pollard's rho (John Pollard, 1975). Verified live: over 3,000 random composites the algorithm finds a nontrivial factor every time — a divisor d with 1 < d < n and n mod d == 0 (window.__rho.factored === true). 8051 -> 97 (8051 = 83x97). The sqrt(p) birthday-collision bound, the Floyd cycle detection, and the gcd reveal are exact; the factor is found without ever computing p directly.
FIG 'The rho' is the literal shape of the hidden cycle (a tail feeding a loop); the birthday collision, the cycle detection, and the gcd trick are real and checked. Rho is efficient for moderate factors, not a break of large-semiprime cryptography — stated honestly, not overclaimed.
FIG 'The rho' is the literal shape of the hidden cycle (a tail feeding a loop); the birthday collision, the cycle detection, and the gcd trick are real and checked. Rho is efficient for moderate factors, not a break of large-semiprime cryptography — stated honestly, not overclaimed.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RAID · David Lee Wise (ROOT0), with AVAN