Trial division to factor a number tries every candidate up to √n — hopeless for large numbers. Pollard’s rho is a clever shortcut: iterate a pseudo-random function f(x) = x² + c (mod n) and, because there are only finitely many residues, the sequence must eventually repeat — looping back on itself into a shape like the Greek letter ρ (a tail leading into a cycle). Run two pointers at different speeds until they collide; the gcd of their difference with n is very likely a real factor. Step the tortoise and hare and watch a factor fall out.
expected O(n^¼) to find a factor · a pseudo-random walk that loops · gcd reveals the factor
f(x) = x²+c mod n
A cheap pseudo-random step whose sequence eventually cycles.
the ρ shape
The sequence has a tail then a loop — draw it and it looks like the letter ρ.
tortoise & hare
Two pointers, one stepping once and one twice, to detect the cycle (Floyd).
gcd reveals a factor
gcd(|x − y|, n) is a nontrivial factor once the runners align modulo a factor.
rho.js — two runners, one collision
Ready
Factoring n = 8051. We iterate f(x)=x²+1 mod n from x=2. A slow tortoise steps once, a fast hare twice. Each step we take gcd(|tortoise − hare|, n). Step to run.
2
tortoise
2
hare
–
gcd
How it works
Two ideas combine. First, a sequence of residues mod n is eventually periodic — it must revisit a value and then loop forever, and drawn out it forms the ρ silhouette. Floyd’s tortoise-and-hare finds that loop cheaply: run one pointer at single speed and another at double, and they’re guaranteed to meet inside the cycle without storing the whole sequence. Second — the subtle part — you don’t actually care about a collision mod n; you care about a collision mod a hidden factor p. Because p is smaller, the sequence cycles mod p much sooner. When tortoise ≡ hare (mod p) but not yet mod n, their difference is a multiple of p but not of n — so gcd(|tortoise − hare|, n) lands on p.
1
Iterate a pseudo-random map
Pick f(x) = x² + c (mod n) and a start value. Its outputs bounce around unpredictably but must eventually repeat, since there are only n possible values.
2
Run tortoise and hare
Advance a slow pointer by one step and a fast pointer by two each round. Floyd’s method guarantees they collide within the cycle, using O(1) memory.
3
Take a gcd every step
Compute d = gcd(|tortoise − hare|, n). Most steps d = 1. But once the two align modulo a hidden factor p, their difference is a multiple of p, so d becomes p — a real factor.
✓
Restart if it fails
Occasionally the pointers collide mod n first, giving d = n (no factor). Then just restart with a different constant c or start value. The expected work to find a factor is about O(n^¼).
Find a factor
~O(n^¼)
Memory
O(1)
Cycle detect
Floyd
vs trial div.
O(√n)
The code
# Pollard's rho: find a nontrivial factor of ndef pollard_rho(n, c=1):
f = lambda x: (x*x + c) % n
x = y = 2
d = 1
while d == 1:
x = f(x) # tortoise: one step
y = f(f(y)) # hare: two steps
d = gcd(abs(x - y), n) # a real factor once they align mod preturn d if d != n else pollard_rho(n, c + 1) # retry on failure
Quick check
1. Why is the sequence f(x), f(f(x)), … guaranteed to eventually repeat?
Every value is a residue mod n, and there are only n of them. By the pigeonhole principle the sequence must revisit a value, after which it repeats forever — forming the ρ shape (a tail into a cycle).
2. Why does gcd(|x − y|, n) reveal a factor?
The sequence cycles modulo a small factor p sooner than mod n. When x and y agree mod p but not mod n, their difference is divisible by p but not by n, so gcd(|x−y|, n) equals p — a real factor.
3. What do the tortoise and hare accomplish?
Running one pointer at single speed and one at double is Floyd’s cycle detection: they are guaranteed to meet inside the loop without storing the sequence, giving Pollard’s rho its O(1) memory footprint.
FAQ
What is Pollard's rho algorithm?
A fast, memory-light algorithm for finding a nontrivial factor of a composite. It iterates a pseudo-random f(x)=x²+c mod n (which eventually cycles) and uses tortoise-and-hare cycle detection plus a gcd to extract a factor — expected ~O(n^¼), far better than O(√n) trial division.
Why is it called 'rho'?
Because the sequence of iterated values, drawn as a path, looks like the Greek letter ρ: a tail of non-repeating values leading into a circular loop (the cycle). The tail is the run-in; the circle is the repeating cycle.
Can Pollard’s rho fail?
Yes, recoverably: sometimes the pointers collide mod n first, giving gcd = n and no factor — just restart with a different c or start value. It also can’t factor a prime, so a primality test (like Miller–Rabin) is usually run first.
How does Pollard’s rho compare to other factoring methods?
Excellent for numbers with a smallish factor and for moderate sizes (competitive programming, light cryptanalysis) at ~O(n^¼) and O(1) memory. For very large numbers with only large factors, the quadratic sieve and general number field sieve dominate; rho often peels off small factors first.