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, for 2 ≤ n ≤ 100000. 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. When 1 < gcd < N, it is a nontrivial factor of N. If the gcd equals N, try another c. Pick a number to break and watch:

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: