Two constants that do not walk at random

A collision that finds a factor walked through the remainders modulo a number $N$ by the rule $x \mapsto x^2 + c$, and found a hidden prime factor $p$ at the moment the walk repeated modulo $p$. The cost of the method is the length of that walk, and every estimate of it assumes that $x^2 + c$ modulo a prime behaves like a function chosen at random: a random function on $p$ values repeats after about $\sqrt{\pi p/2}$ steps, by exactly the arithmetic of twenty-three people. That essay measured the assumption for $c = 1$ and found it held, and it closed on the question of why.

There is a sharper way to ask. The textbooks that describe Pollard’s method add a caution: do not use $c = 0$, and do not use $c = -2$. For those two constants the method is much slower. So the question is not only why $x^2 + c$ looks random, but why it looks random for every constant except two — and whether its obvious departure from randomness, that it is two-to-one, should have mattered and does not.

Four constants, two behaviours #

For $c = 1$ and $c = 3$ the staircase of walks still running lies on the birthday curve. The mean number of steps before a repeat is within a few per cent of $\sqrt{\pi p/2}$, and the spread matches too. For $c = 0$ and $c = -2$ the staircases are in a different place altogether: half the walks are still running at ten times the random length, and some run a hundred times longer.

Such a walk is shaped like the Greek letter ρ — a tail of values visited once, then a cycle run round for ever — and the random function’s tail and cycle are each about $0.63\sqrt p$ on average. The long walks for $c = 0$ and $c = -2$ are long in a particular way, and that is the clue to what they are.

A walk that is really a multiplication #

For $c = 0$ the map is squaring, and squaring is a multiplication. The nonzero remainders modulo a prime form a cyclic group of order $p - 1$: one residue has powers that are all of them, a primitive root $g$, so every $x$ is $g^a$ for some exponent $a$. Squaring sends $g^a$ to $g^{2a}$. The walk $x_0, x_0^2, x_0^4, \ldots$ is the walk $a, 2a, 4a, \ldots$ in the exponent, taken modulo $p - 1$.

That walk is not random at all. Write the order of $x_0$ as $2^s m$ with $m$ odd. Doubling the exponent kills one factor of 2 from the order each step, so after $s$ steps the value has odd order $m$ — that is the tail, and it is short, since $s$ is at most the number of factors of 2 in $p - 1$. From then on the walk runs round a cycle whose length is the number of doublings that bring an exponent back to itself modulo $m$: the multiplicative order of 2 modulo $m$. For $p = 53$ and $x_0 = 2$, the order of 2 is 52, so $s = 2$ and $m = 13$, and the order of 2 modulo 13 is 12. The figure’s tail of 2 and cycle of 12 are exactly those numbers.

Across 300 primes the prediction is exact every time. The order of 2 modulo a large odd number is typically comparable to the number itself, not to its square root, so the cycles of the squaring walk are typically of size proportional to $p$ — which is why the $c = 0$ staircase sits so far to the right. A random function’s cycle has length about $\sqrt p$; the squaring walk’s has length about $p$ divided by small factors. Nothing about it is a birthday coincidence. It is an orbit of doubling in a cyclic group.

How long the exceptional cycles are #

How far to the right the $c = 0$ staircase sits is a question about the order of 2 — the same quantity that, run the other way, proves a number prime — and it is one of the classical questions of number theory. Emil Artin conjectured in 1927 that 2 is a primitive root — has the largest possible order, $p - 1$ — for a positive proportion of primes, about 37.4 per cent of them, and Christopher Hooley proved the conjecture in 1967 assuming a generalised Riemann hypothesis. For those primes the squaring walk from a typical start has a cycle of length about $(p - 1)/2^s$, a fixed fraction of $p$.

Even for primes where 2 has smaller order, the order is rarely small: for almost every prime it exceeds $\sqrt p$ by a wide margin, as Paul Erdős and Ram Murty showed. So the squaring walk’s cycles are not just longer than a random function’s on average — they are longer by a factor that itself grows with $p$, like $\sqrt p$ divided by small numbers. At primes near 150,000 that factor is in the tens and hundreds, which is what the survival staircase shows.

The exceptions are therefore worse the larger the prime, and that is the practical point. A walk that is merely somewhat slower than random would cost Pollard’s method a constant factor; a walk whose length is proportional to $p$ costs it the square root it was designed to save.

The other exception #

The constant $-2$ is the same phenomenon in a different coordinate. Write $x = z + 1/z$. Then

$$x^2 - 2 = z^2 + 2 + \frac{1}{z^2} - 2 = z^2 + \frac{1}{z^2},$$

so $x \mapsto x^2 - 2$ is squaring in $z$, seen through the change of coordinates $z \mapsto z + 1/z$. Over the real numbers this is the familiar identity $2\cos 2\theta = (2\cos\theta)^2 - 2$, which makes $x^2 - 2$ on $[-2, 2]$ the angle-doubling map of a solvable chaos. There the doubling of an angle is the model of sensitive dependence: two nearby angles separate at a rate of two per step, and the orbit of a typical point is as unpredictable as a coin. Modulo a prime the same doubling runs in a finite cyclic group, where it cannot be unpredictable — it is periodic, with period an order of 2 — and it is exactly this periodicity that makes the walk a poor imitation of a random function. The real map is chaotic because doubling is; the modular map is regular because doubling is. Modulo a prime, for each $x$ the equation $z + 1/z = x$ has a solution $z$ either among the remainders themselves, in a group of order $p - 1$, or in a quadratic extension, in a group of order $p + 1$. Either way the walk is doubling in a cyclic group, and its cycles are orders of 2 modulo the odd parts of $p - 1$ or $p + 1$.

These are the only two such constants. A map $x^2 + c$ that is conjugate to a group homomorphism must be squaring in some coordinate, and the polynomials of degree two with that property are, up to change of variable, $x^2$ and the Chebyshev polynomial $x^2 - 2$. Every other constant gives a quadratic map with no such structure, and as far as anyone can tell its walks are as unstructured as a random function’s.

Tails and cycles #

The two shapes are unmistakable side by side. For $c = 1$, tails and cycles are both of order $\sqrt p$, scattered in the way the birthday model predicts — a random function’s first repeat lands uniformly on the values already seen, so the split between tail and cycle is uniform too, and both average $\sqrt{\pi p/8} \approx 0.63\sqrt p$. For $c = 0$ the letter ρ has lost its tail: the walk falls onto its cycle in a handful of steps, one for each factor of 2 in the order of the start, and then circles for a time set by number theory.

The contrast explains the textbook advice. Pollard’s method detects the repeat modulo $p$ by comparing values a growing distance apart, and it costs about as many steps as the tail plus the cycle. A walk that is a multiplication has cycles of length comparable to $p$ rather than $\sqrt p$, and using it throws the method’s whole advantage away.

Two-to-one, and random anyway #

Every $x^2 + c$ has a property no random function has: it is two-to-one. The values $x$ and $-x$ always go to the same place, so only about half of the remainders are values of the map and the other half are never reached. A random function reaches about $1 - 1/e \approx 63$ per cent of its values. It would be natural to expect this to change the walks, and it does not.

The walk repeats when two different values it has visited are sent to the same place, and the chance of that, for a pair of values, is the chance that a random point’s image coincides with another’s. If the number of preimages of a value is $d$, that chance is proportional to the average of $d(d - 1)$, which is the variance of $d$ when its mean is 1. For a random function $d$ has the Poisson distribution with mean 1 and variance 1. For a two-to-one map $d$ is 0 or 2 with equal chance: mean 1, variance 1. The two collide at the same rate, and the birthday arithmetic gives the same $\sqrt{\pi n/2}$ for both.

The figure checks the general rule by building random maps with $r$ preimages per value, for which the variance is $r - 1$ and the predicted length is $\sqrt{\pi n/2}$ divided by $\sqrt{r - 1}$. The measured lengths follow it: three-to-one maps walk about 0.71 times as far, four-to-one 0.55, six-to-one 0.44. Two-to-one is the one uneven structure that happens to cost nothing.

The difference does show up elsewhere. Apply a map to every value, then again to the result, and count what is left: a random function keeps about 63 per cent after one application, and the survivors shrink towards the cycles at a rate set by the same variance. A two-to-one map keeps exactly half after one application, a visibly different number. So $x^2 + c$ is distinguishable from a random function by a statistic that looks at the whole map at once. The walk from a single starting point never computes such a statistic. It sees one value at a time, and the only question it asks — has this value appeared before — depends on the map only through the chance that two visited values share an image. That is a lucky fact for Pollard, and it is the same kind of fact as unevenness bringing a birthday match sooner: what matters is a second moment, not the shape of the distribution.

What the method pays for a walk #

Pollard’s method never sees the walk modulo $p$; it sees the walk modulo $N$, and detects the repeat modulo the hidden $p$ by computing a greatest common divisor of $N$ with the difference of two values. The standard way to find a repeat without storing the walk is to move two copies of it, one twice as fast as the other, and compare them after each step — the tortoise and hare. They meet within tail plus cycle steps of the start, so the method’s cost is set by the tail plus the cycle, the whole length of the letter ρ.

For a random-looking constant that length is about $1.25\sqrt p$, which is where the method’s famous cost of $p^{1/2}$ operations, or $N^{1/4}$ for the smallest prime factor of a two-prime $N$, comes from. For $c = 0$ the tail is short but the cycle is a sizeable fraction of $p$, and the tortoise and hare must run round most of it before they meet: the method becomes no better than trial division by every prime up to $p$. That is why the constant is chosen at random from the safe ones and changed if a run fails, and why no implementation uses 0 or $-2$.

The first collisions, proved #

Some of this is a theorem. Eric Bach proved in 1991 that for $x^2 + c$ with $c \ne 0, -2$, the chance of a collision among the first $k$ values, averaged over primes and starting points, is what a random function gives — about $\binom{k+1}{2}/p$ — as long as $k$ is small beside $p^{1/4}$. The figure measures the same ratio and finds it close to 1, and continuing close to 1 well beyond $p^{1/4}$, which is about 10 for these primes.

The proof works by counting: two values of the walk coincide exactly when a certain polynomial in the starting point vanishes modulo $p$, and for the first few steps those polynomials are of small degree and have no reason to share roots except in the cases $c = 0$ and $c = -2$, where the group structure makes them factor. Beyond $p^{1/4}$ the degrees grow too fast for the counting to control, and the argument stops — just short of the $\sqrt p$ scale at which Pollard’s method actually finishes.

What the figures cannot show #

Every measurement here averages over primes and starting points, and a random function’s statistics are also averages. What cannot be measured is a statement about a single prime: that for this $p$, the walk from this start is typical. The evidence is that nothing atypical has been seen in any range searched except the two constants explained above, which is persuasive and is not a proof.

The random maps in the figures are also a model. A real $x^2 + c$ is a fixed polynomial, not a random two-to-one map, and the agreement is between the polynomial’s statistics and the model’s averages. That is what “behaves like a random function” means in this subject; it is a statement about distributions across many primes, not about any particular walk.

And the survival curves for $c = 0$ and $c = -2$ reflect the distribution of multiplicative orders of 2, which is itself a deep subject. How often 2 has large order modulo the odd part of $p - 1$ is tied to Artin’s conjecture on primitive roots, open in general and known only under a generalised Riemann hypothesis.

Still open: a proof at the scale that matters #

The heuristic that $x^2 + c$ behaves like a random function, for $c \ne 0, -2$, is the foundation of the running-time estimate $O(\sqrt p)$ for Pollard’s method, and it is not proved. Bach’s theorem reaches $p^{1/4}$; the walk finishes at $p^{1/2}$. No argument is known that controls the collisions of a fixed polynomial map across that gap, for all primes or even for almost all.

The question is one instance of a broader one: whether a specific, simple map on a finite set is as unstructured as a random one. Proving that a particular algorithm’s output cannot be told from random runs into the same wall, and so does proving that a hash function built from simple operations has no exploitable pattern. In each case the structured exceptions — here, the two constants that are multiplications — can be found and explained, and the absence of any other structure is believed and unproved.

What a multiplication hides #

The walk $x^2 + c$ is deterministic, and for two constants its determinism is visible: the orbits are powers of 2 in a cyclic group, and their lengths are orders, computable in advance, with no randomness in them. For every other constant the determinism is invisible, and the walk collides exactly as often as chance would make it — even though the map sends $x$ and $-x$ to the same place and reaches only half the values, because the one number the collisions depend on, the variance of the number of preimages, is the same for a two-to-one map as for a random one.

That is what Pollard needs and what nobody can prove. The walks behave like random functions for the reason random functions behave as they do — a second moment and the birthday arithmetic — and the reason the two exceptions do not is that they are secretly a multiplication, and a multiplication remembers everything.