The site's eighth Number Theory entry, and the first to answer a genuinely different
question than the other seven. Miller–Rabin
and Sieve of Eratosthenes both decide whether
a number is prime. Pollard's rho starts from the opposite premise — n is known composite —
and asks for an actual nontrivial divisor. That's a different job: knowing 8,051 isn't prime doesn't hand
you 83 and 97, and trial division (checking every candidate up to √n) is the naive way to get them, at a
cost that's fine for small n and hopeless once n has dozens of digits. RSA key generation needs the first
kind of test on its own huge candidates; an attacker trying to break a small or badly-generated key needs
the second.
John Pollard published the algorithm in 1975. The name comes from its behavior, not its author twice
over — visualize the sequence x0, x1, x2, … generated by
repeatedly applying a simple pseudorandom function; because there are only finitely many values mod
n, the sequence must eventually repeat, and once it does, it cycles forever. Plotted with each value
as a node and each step as an arrow, the shape looks like the Greek letter ρ — a tail leading into a loop.
Let p be the smallest prime factor of n (unknown to the algorithm). The
sequence xi mod p also cycles — and because p is so much smaller than
n, it cycles much sooner, in roughly O(√p) steps by the same birthday-paradox
reasoning that makes hash collisions common far before a hash table fills up (the same argument
Miller–Rabin's Rabin bound and
HyperLogLog's cardinality estimate both lean on in their own
ways). So long before xi mod n itself repeats, two terms xi
and xj that look completely different mod n can already agree mod
p — meaning p divides xi − xj even though
n doesn't. Computing gcd(|xi − xj|, n) at exactly that
moment finds p (or a multiple of it) without ever knowing what p is in advance.
Finding that colliding pair without storing the whole sequence is Floyd's tortoise-and-hare cycle
detection: keep two pointers into the same sequence, one (the tortoise) advancing one step at a time, the
other (the hare) advancing two. If there's a cycle, the hare eventually laps the tortoise — and checking
gcd(|tortoise − hare|, n) after every step is enough to catch the mod-p collision
the moment it happens, using O(1) extra memory.
Enter a composite n and a constant c for the pseudorandom step function
f(x) = x² + c mod n, then step through the tortoise-and-hare race. 8051, c = 1
succeeds in 3 steps (83 × 97). 8051, c = 5 is the same number with a different constant —
watch it run all the way to a full cycle collapse instead of finding a factor, the case covered in
Pitfalls below. 4, c = 1 shows the algorithm failing outright on a
tiny power of two. 9998000099, c = 2 (= 99,989 × 99,991) is a larger example — 37 steps
instead of 3, but still nowhere near the ~100,000 trial division would need to reach 99,989 by brute force.
tortoise x, hare y, gcd(|x−y|, n) — oldest to newest:
Each step computes x = f(x) once (the tortoise) and y = f(f(y)) twice (the
hare), then checks d = gcd(|x − y|, n). Three outcomes are possible:
d = 1 — no collision mod any factor of n yet. Keep going.1 < d < n — a genuine nontrivial factor. d (or n / d) is a
proper divisor of n; recurse on each half until every piece is prime.d = n — the tortoise and hare collided mod n itself before ever colliding mod
just one factor. The run has failed to produce a factor, not because the algorithm is wrong but because
this particular (c, x0) pair happened to send the whole sequence into a cycle too
early. The fix is simple: pick a different c (or starting point x0)
and try again. This isn't a rare corner case — it's checked directly in Pitfalls
below, and it's why every real implementation wraps the core loop in a retry.Unlike every other entry in this category, this bound is a heuristic, not a proven
worst case — it relies on f(x) = x² + c mod p behaving enough like a genuinely random function
that the birthday argument applies. That assumption has no proof, but it has held up empirically for
decades of use, including in real integer-factorization records.
function gcd(a, b) {
a = a < 0n ? -a : a;
b = b < 0n ? -b : b;
while (b) { [a, b] = [b, a % b]; }
return a;
}
function pollardRhoOnce(n, c) { // one attempt with a fixed constant c, x0 = 2
const f = x => (x * x + BigInt(c)) % n;
let x = 2n, y = 2n, d = 1n;
while (d === 1n) {
x = f(x);
y = f(f(y));
d = gcd(x > y ? x - y : y - x, n);
}
return d === n ? null : d; // null = collapsed, caller should retry with a new c
}
function isPrime(n) { // trial division — fine for the small cofactors
if (n < 2n) return false; // recursion bottoms out on
for (let i = 2n; i * i <= n; i++) if (n % i === 0n) return false;
return true;
}
function factorize(n) {
if (n === 1n) return [];
if (n % 2n === 0n) return [2n, ...factorize(n / 2n)];
if (isPrime(n)) return [n];
let d = null, c = 1n;
while (d === null) d = pollardRhoOnce(n, c++); // retry with the next constant on collapse
return [...factorize(d), ...factorize(n / d)];
}A production factorizer would replace isPrime's trial division with
Miller–Rabin — by the time rho has peeled a
large number down to a plausible-prime cofactor, that cofactor can still be far too big for trial division
to check quickly, even though rho itself found it fast.
A run can collapse without finding a factor — that's normal, not a bug. n = 8,051 with
c = 1 finds 97 in 3 steps. The exact same n with c = 5 runs the tortoise and hare through 14 steps and they
land on the identical value (x = y = 4852), so |x − y| = 0 and
gcd(0, 8051) = 8051 = n — a collapse, not a factor. This is checked directly, not just
claimed: the demo's second preset traces exactly this run. The fix the reference implementation above uses
is a plain retry loop over increasing c; c = 5 is simply an unlucky choice for this
n, not evidence the algorithm is broken.
The algorithm degenerates on tiny numbers and powers of small primes. n = 4 with c = 1
collapses in 2 steps (x = y = 2, gcd(0, 4) = 4) — checked directly, and every
other c from 0 to 5 fails the same way on n = 4. There simply isn't enough room in
{0, 1, 2, 3} for the birthday argument to find a mod-2 collision before the tortoise and hare
collide mod 4 outright. This is why the reference implementation's factorize pulls out factors
of 2 with plain division before ever calling rho, and production factorizers trial-divide by a
handful of small primes first for the same reason — rho is the right tool for a large, otherwise-stubborn
factor, not for the small ones that trial division already finds instantly.
Rho needs to know n is composite before it starts — feeding it a prime doesn't fail
loudly. Run the core loop on a prime and there's no factor to find, ever: d will
eventually hit n itself (a collapse) after wasting real work, since a prime has no proper
divisor greater than 1 for any collision to expose. factorize above avoids this by checking
isPrime(n) before ever calling pollardRhoOnce — skipping that check doesn't
produce a wrong answer so much as an expensive way to rediscover that a number was prime all along.
O(n1/4) expected modular operations to find the smallest prime factor
p of a composite n, heuristically — the birthday bound gives O(√p) steps, and in
the worst case (n a product of two roughly equal primes) p ≈ √n, so O(√p) ≈ O(n1/4).
Each step is one modular squaring, so the bit-operation cost is O(n1/4 log² n). That heuristic
bound is why rho matters at all: for a 40-digit semiprime, √n has roughly 20 digits — trial division at
that scale is astronomically infeasible — while n1/4 has roughly 10 digits, still large but
searchable. It isn't the fastest known general-purpose factoring method (the quadratic sieve and general
number field sieve both beat it asymptotically on large inputs), but its O(1) memory footprint and small
constant make it the practical first attempt for finding small-to-medium factors before reaching for
something heavier.
This site's guide, Choosing a Number Theory Algorithm, compares this entry against the other thirteen Number Theory entries side by side.