The Shape of the ρ
Pollard's 1975 method factors a number by walking a simple loop — square, add one, take the remainder — until the walk catches its own tail. The walk always makes the shape of the Greek letter it's named for. Here is that shape, the factor that falls out of it, and the birthday-paradox reason it's fast.
Take a modulus n and the map f(x) = x² + c (mod n). Start anywhere and apply it over and over. Because every input has exactly one output and there are only finitely many residues, the orbit must eventually revisit a value it has already seen — and from then on it loops forever. So every orbit looks the same: a tail running in, then a cycle it can never leave. That picture — a stem feeding a loop — is the lowercase Greek rho, ρ, and it is exactly why John Pollard called his method the rho method.
I · Draw the ρ
Trace any residue's orbit under x²+c mod n. The dots are the values it visits; the orbit walks down the stem and around the loop it lands in.
II · The factor falls out
Now the trick. Pollard runs two walkers on the same orbit — a tortoise that steps once, a hare that steps twice — and at each step computes gcd(|tortoise − hare|, N). While that gcd is 1, nothing has happened. The instant it jumps above 1, it is a factor of N. Pick a number to break and watch:
The lower track is the same orbit reduced modulo the smaller secret factor p — the rho you can't see from outside. Watch where it closes its loop: that early collision, invisible in the full number, is the one the gcd reports.
III · Why it's fast — the birthday √n
A walk mod n closes its loop after about √(πn/2) ≈ 1.25·√n steps — the same square-root law as the birthday problem (you only need ~√(days) people to get a shared birthday). For a number N = p·q, the hidden walk mod the smaller prime p closes after only ~√p steps — long before the walk mod N would — and that is what the gcd catches. So Pollard's method finds a factor in about N^(1/4) steps, not the √N of trial division. Choose a prime and measure it:
Two values of c break the law, and they are the
two every textbook tells you to avoid: c = 0 (the map
x→x²) and c = −2 (the
Lucas–Lehmer map). Their orbits are governed by
multiplicative order, not chance, so they don't behave like a random walk at all —
and this is now proven, not just observed. Squaring is the doubling map
on the exponent of Fp*, so its periodic points are
exactly the elements of odd order; and x²−2, through the
Chebyshev change of variable x = y + 1/y, becomes
y → y² on two groups at once (orders
p−1 and p+1) — the reason it strays
even further than c = 0. The exact counts are pinned and
certified two ways in
research/pollard-rho/special-c.md.
The check
Everything on this page is recomputed live, and the same engine is verified from
scratch in research/pollard-rho/verify.mjs (26/26): the graph counts
agree with an independent brute force for all n ≤ 200; Pollard's rho factors
a battery of semiprimes up to ~9.2×10¹⁸; the mean rho length over all generic
c lands within ~3% of √(πp/2); and the two degenerate maps are
certified as theorems — periodic points of x→x² mod p = 1 + oddpart(p−1)
and periodic points of x²−2 mod p = (oddpart(p−1)+oddpart(p+1))/2 — each
checked both by formula and by building the periodic set from group theory and matching
it element-for-element to the graph the walker finds, for every prime
p < 2000. The derivation is
research/pollard-rho/special-c.md.
Counting the structure of this map turned up new arithmetic, too. The number of
cycles of x²+1 mod n is catalogued as
OEIS A352635, which our engine reproduces
exactly — but its sibling, the number of periodic points, is absent from
OEIS (checked 2026-06-25), as are two summed-over-c invariants. All
three are staged with reproducible code and a b-file in
oversight/oeis/pollard-rho-x2plus1/:
periodic points of x²+1 mod n = 1,2,1,2,3,2,2,2,3,6,2,2,6,4,3,2,6,6,2,6,…