Pollard's Rho — Factoring by Cycle Detection

Walk x ← (x² + c) mod n. The tortoise (1 step) and hare (2 steps) chase around the ρ-shaped orbit; gcd(|x − y|, n) pops out a factor.

round 0

The ρ orbit (sequence mod n)

tortoise x (1 step) hare y (2 steps) factor found
no factor yet — gcd is still 1

Iteration & gcd

f(x) = (x² + 1) mod 8051
tortoise x = 2   hare y = 2
gcd(|x − y|, n) = gcd(0, 8051) = 1
Press Step to begin. Each round advances the tortoise once and the hare twice, then computes gcd(|x − y|, n). When that gcd lands strictly between 1 and n, it is a nontrivial factor.
Self-contained visualization. The sequence x ← (x² + c) mod n is deterministic but pseudo-random; reduced modulo a hidden prime p | n it collides after about √p steps (birthday paradox), so gcd(|x − y|, n) reveals a factor in expected O(n1/4) time. A gcd of n is a collapse — restart with a new c. See junior.md and professional.md for the proof.

Try n = 8051 (= 83 × 97) with c = 1 to watch the factor pop out in a few rounds, or change c to see a different orbit. A real implementation uses an overflow-safe mulmod (__int128 / Montgomery) and pairs rho with Miller-Rabin (sibling 08) to fully factor by recursion. This demo keeps n small so products stay exact in double-precision integers.