A collision that finds a factor

The birthday problem is usually met as a hazard. A room of twenty-three probably contains a coincidence nobody arranged, a hash function with $2^{128}$ outputs probably yields two colliding documents after only $2^{64}$ tries, and the square root in both is the reason collisions arrive far sooner than intuition expects.

In 1975 John Pollard turned the hazard into a tool. He wanted to factor a number $n$ and he knew that a collision among remainders modulo an unknown factor $p$ would arrive after about $\sqrt p$ steps — long before a collision modulo $n$ itself. The difficulty is that $p$ is unknown, so the remainders modulo $p$ cannot be computed and the collision cannot be looked for. The method’s whole content is a way of detecting a coincidence in numbers nobody can see.

A walk that has to come back #

Pick a modulus $m$, a constant $c$, and a starting value, and apply $x \mapsto x^2 + c \bmod m$ over and over. There are only $m$ possible values, so by the pigeonhole principle some value must recur within $m+1$ steps. And because each value determines the next, the moment a value recurs the walk is trapped: from then on it retraces the same stretch forever.

That forces the shape in the figure. Some number $\mu$ of values form a tail, visited once; the rest form a cycle of length $\lambda$. The picture looks like the Greek letter rho, which is where the method’s name comes from, and the same shape appears whenever a deterministic process runs in a finite space — an orbit that must come back in a system with finitely many states is a rho with its tail and loop.

What pigeonhole does not say is when. It guarantees a repeat within $m+1$ steps. The walk above repeats after nineteen, out of a possible 338, and that is typical rather than lucky.

Why the first repeat is a birthday #

Suppose the map were not $x^2 + c$ but a function chosen completely at random from all functions on $m$ values. Then the walk’s successive values would be independent uniform draws for as long as it keeps visiting new values — each step applies the function to a point it has never been applied to before, and a random function’s value at a fresh point is a fresh random number.

So the walk keeps producing new values exactly as long as a sequence of independent draws avoids every earlier draw. The step at which it first repeats is the moment a room of people first contains a shared birthday, with $m$ days in the year. The chance of lasting past $k$ steps is the familiar product $\tfrac{m-1}{m}\cdot\tfrac{m-2}{m}\cdots$, and the expected number of distinct values before the repeat is about $\sqrt{\pi m/2}$ — the same $\sqrt{\pi d/2}$ that gives the average room size at which a match first appears.

That is a derivation about random functions, and $x^2 + 1$ is not one. It is a single, very specific polynomial, and nothing in the argument above applies to it.

The polynomial behaves as though it were random. Across four hundred primes its first-repeat time has the birthday distribution to within the sampling wobble of four hundred draws, and its mean lands within one per cent of the random-function value. This is an observation and not a theorem. Nobody has proved that $x^2 + c$ has rho lengths of order $\sqrt p$ for all primes, or for most of them, and the whole running-time analysis of the method rests on the observation. It is one of the better-supported unproved heuristics in computational number theory, and it is unproved.

There is also a reason to expect the fit to be imperfect. A square has two square roots, so $x^2 + c$ is two-to-one: half the values modulo $p$ have no predecessor at all and can only ever be a starting point. A genuinely random function has no such constraint. That the distribution still matches as closely as it does says the constraint barely affects when the first repeat happens — the walk never gets far enough into the space for the missing preimages to matter.

Finding the repeat without remembering the walk #

To detect a repeat, the obvious method stores every value and checks each new one against the store. That needs memory proportional to the walk’s length, and at the sizes where the method is useful, $\sqrt p$ values may be billions.

Robert Floyd’s alternative stores two numbers. Run two copies of the walk from the same start: a tortoise that takes one step at a time and a hare that takes two. Once both are on the cycle, the hare gains one position per step, so it must catch the tortoise within one lap.

The meeting step has a clean characterisation. The tortoise at step $i$ and the hare at step $2i$ hold the same value exactly when both are on the cycle and the gap $i$ between their positions is a multiple of $\lambda$. So the first meeting is at the smallest multiple of $\lambda$ that is at least $\mu$, which is never more than $\mu + \lambda$ — the length of the rho. Floyd’s method finds the repeat at most one lap late, using constant memory.

The price is a factor of about three in steps, since each round moves the hare twice and the tortoise once. Richard Brent’s variant, which teleports the tortoise to the hare at each power of two instead, is usually a quarter to a third faster and is what practical implementations use. Neither changes the square root.

The shadow walks #

Now take $m = n$, the number to be factored, and suppose $n = pq$ with $p$ and $q$ unknown primes. Run the walk modulo $n$.

The crucial property of $x^2 + c$ is that it respects reduction. If $x \equiv y \pmod p$ then $x^2 + c \equiv y^2 + c \pmod p$, because a polynomial with whole-number coefficients commutes with taking remainders. So the walk modulo $n$, reduced modulo $p$, is the walk modulo $p$ — a shadow walk on only $p$ values, running in lockstep with the visible one. The same is true modulo $q$. That is exactly the correspondence two dials turning at once describes: a residue modulo $n$ is a pair of residues modulo $p$ and $q$, and a polynomial map acts on each dial separately.

The shadow modulo $p$ closes its rho after about $\sqrt p$ steps. The visible walk modulo $n$ does not close until about $\sqrt n$ steps — much later. In between, there are tortoise and hare values $x_i$ and $x_{2i}$ that agree modulo $p$ but not modulo $n$, so $p$ divides $x_{2i} - x_i$ and $n$ does not. And that is visible: the greatest common divisor of $x_{2i} - x_i$ with $n$ is $p$, or at least a proper factor of $n$, computed by Euclid’s algorithm with no knowledge of $p$ at all.

The two grey columns are the heart of the picture and the one thing the algorithm cannot see. It computes only the tortoise, the hare and one greatest common divisor per step. The coincidence happens entirely in a residue system defined by a number nobody knows, and the divisor computation reads it out.

The second table makes a point the arithmetic might hide. The method does not find the smallest factor; it finds whichever shadow’s rho is detected first. The expected time favours the smaller prime, since $\sqrt{613}$ is less than $\sqrt{743}$, but the two are close and each rho length is a random-looking quantity with a wide spread, so either can win. When a number’s prime factors differ greatly in size, the smallest wins nearly always.

And there is a failure case worth naming. If both shadows close at the same step, the difference is divisible by $p$ and $q$ both, the divisor is $n$ itself, and nothing has been learned. The remedy is to change $c$ and start again, which gives new and effectively independent walks.

Two constants to avoid, and why #

Implementations are told never to use $c = 0$ or $c = -2$, and the reasons are different and both worth seeing.

With $c = 0$ the walk is $x \mapsto x^2$, so the $k$-th value is $x_0^{2^k}$. Its rho is governed entirely by the multiplicative order of $2$ modulo divisors of $p - 1$ — a clean algebraic structure, which is precisely what the method does not want. A structured walk can have a very long tail or a very long cycle for a particular prime, and nothing about its length is birthday-like.

With $c = -2$ the structure is less obvious and more beautiful. Write $x = t + t^{-1}$; then $x^2 - 2 = t^2 + t^{-2}$. The map squares $t$, which is the same doubling that makes the logistic map at parameter four solvable, where $4x(1-x)$ turns out to be the Chebyshev polynomial $2u^2 - 1$ in disguise. The walk $x^2 - 2$ is therefore a disguised $x^2$, and inherits its algebraic orbit lengths.

The one polynomial family that makes a chaotic map exactly solvable is the one that makes a factoring walk fail, and for the same reason: being solvable and being random are opposites, and Pollard’s method needs the second.

What it costs #

If the shadow modulo $p$ behaves like a random function, its rho is about $\sqrt{\pi p/2}$ values long, and Floyd’s search spends a small multiple of that. So the cost depends on the size of the factor, not of the number being factored.

The scatter around the line is not noise in the measurement; it is the spread of the rho length itself, which for a single prime ranges over a factor of several. Averaged across sixty products the slope is close to a half. The point well below the line near $p = 10^5$ is a product whose larger factor’s shadow closed very early — the same effect as the 743 above, at a larger scale.

The comparison with trial division is the reason the method mattered. Dividing by every candidate up to $p$ costs about $p$ operations. Pollard’s method costs about $\sqrt p$. A twelve-digit number with a six-digit factor takes hundreds of thousands of trial divisions and something over a thousand steps of the walk. Before the elliptic-curve method arrived in 1985, Pollard’s rho was the standard way to strip medium-sized factors off a large number, and in 1980 Brent and Pollard used it to factor the eighth Fermat number, $2^{256} + 1$, finding a sixteen-digit factor.

What the square root does not do is threaten well-chosen cryptographic keys. An RSA modulus is a product of two primes each around $10^{300}$, and $\sqrt{10^{300}}$ is $10^{150}$ steps. The method is decisive against numbers with a small factor and irrelevant against numbers designed to have none, and factoring as a whole remains hard in exactly the cases that matter.

One divisor computation in a hundred #

The tables compute a greatest common divisor at every step, and in practice nobody does. A divisor computation on numbers of a few hundred digits costs far more than a squaring, and at every step but the last it returns 1.

The standard repair uses the fact that a divisor of a product is visible in the product. Multiply the differences $x_{2i} - x_i$ together modulo $n$ for a hundred steps, then take one divisor of the accumulated product with $n$. If $p$ divided any one of the hundred differences, it divides the product, and the single computation finds it. The cost falls to one divisor computation per hundred steps, plus a hundred cheap multiplications.

There is one way this goes wrong, and it is the same failure as before in a new place. If $p$ divides one of the hundred differences and $q$ divides a later one, the accumulated product is divisible by both, and the divisor is $n$. The fix is to back up: return to the start of the batch and take divisors one step at a time until the first non-trivial one appears. Since that happens only on the last batch, it costs at most a hundred extra computations once.

Batching changes nothing about the square root, and it is worth noticing why it is allowed at all. The method never needs to know which step produced the coincidence, only that one did. A procedure that tested each candidate separately would have to test them separately; a procedure looking for a coincidence among many can pool them, because a common divisor is preserved by multiplication in a way that almost nothing else is.

Collisions sought for their own sake #

The rho idea applies to anything that can be iterated, and the most direct application goes back to where this essay began: finding two inputs a hash function sends to the same output.

Iterate the hash on its own output, starting anywhere. The walk lives in a space of $2^{b}$ values for a $b$-bit hash, so it closes a rho after about $2^{b/2}$ steps, and the two distinct values that lead into the joining point of the rho — the last value of the tail and the last value of the cycle — hash to the same thing. That is a collision, found with constant memory, which is exactly the saving the first calculation of the birthday bound noted a naive attack needed.

Paul van Oorschot and Michael Wiener made it parallel in 1994. Many machines each run a walk from a different start and report only distinguished points — values with, say, their first thirty bits equal to zero. Two walks that ever meet are identical from then on, so they reach the same distinguished point, and a central list of those points detects the merge. The work is shared across the machines with almost no communication, and it is the standard way a generic collision search — or a discrete-logarithm search of the kind below — is spread across many machines.

The idea outlived the factoring application, and its most important use now is in a different problem entirely.

The discrete logarithm problem asks, given $g$ and $h = g^x$ in a group of order $N$, for $x$. Pollard adapted the rho walk in 1978: walk through elements of the form $g^a h^b$, tracking the exponents $a$ and $b$, and wait for a collision $g^a h^b = g^{a'} h^{b'}$. The collision gives a linear equation for $x$ modulo $N$. Its expected time is again a birthday time, about $\sqrt{\pi N / 2}$ steps, with constant memory.

For the elliptic-curve groups used in modern public-key cryptography, this is the best general attack known. It is why a curve over a field of about $2^{256}$ elements provides about 128 bits of security rather than 256: the attacker’s work is the square root of the group’s size, set by the same birthday arithmetic that sets a hash function’s collision resistance. Every such system’s key length is chosen with this walk in mind.

What the tables leave out #

The rho figures are drawn modulo primes small enough to fit on a page, and at that size the method is pointless — a prime of 337 is found faster by dividing. The drawings show the shape the argument relies on, not a regime where the method earns its keep.

The tables show columns the algorithm cannot compute. That is their purpose, and it is also a hazard: the reader sees why the divisor becomes 97 at step three, while the method itself sees only that it did. Nothing in a run tells the method how close it is to success, which is why its running time can only be stated as an expectation.

And the cost figure is an average over sixty products, fitted with a line. It shows that the typical cost follows $\sqrt p$ closely enough to be useful. It does not show that any particular number will be split in about $\sqrt p$ steps, and it cannot show the thing the analysis would need, which is a proof that the walk behaves randomly at all.

Still open: why a polynomial walks like a random function #

Every running-time claim above assumes that $x^2 + c$ modulo a prime has rho lengths distributed like a random function’s. The evidence is overwhelming and the proof is missing. Eric Bach showed in 1991 that the first few collisions occur at the rate a random function would give — the probability of a collision within $k$ steps is about $\binom{k}{2}/p$ for $k$ small compared with $p^{1/4}$ — but the argument does not reach the $\sqrt p$ scale where the method actually finishes.

The difficulty is that the walk is deterministic and its values are polynomials of rapidly growing degree in the starting point, and bounding when two of them coincide modulo $p$ for most primes is a question about the distribution of roots of those polynomials. Proving that a specific simple map is as unstructured as a random one is the same kind of question as proving that a generator is unpredictable: easy to test, easy to believe, and without a general method.

A coincidence in numbers nobody can see #

The method is worth keeping for its logic more than its speed. It exploits a coincidence it cannot observe, in a residue system defined by a number it does not know, and it converts that coincidence into something observable by a greatest common divisor — the one computation that reports on a hidden divisor without needing to name it.

And its cost is a birthday cost for a precise reason. The shadow walk is a sequence of values in a space of size $p$, and a sequence of values in a space of size $p$ first repeats after about $\sqrt p$ of them, whether the values are birthdays, hash outputs or remainders of a squared number. The room of twenty-three and the eight-digit factor are the same event at two scales, and Pollard’s contribution was noticing that a coincidence which is a nuisance in one setting is, in another, the whole of the work.