Pollard's rho, worked on a small curve

The attack page gives the idea and the cost. This page runs it: on a curve with 10,039 points it follows one walk until it repeats, recovers the key from the repeat, and then measures how long such walks take on average.

Curve
y2 = x3 + 3x + 6 over F10007
Group
10,039 points, a prime
This walk
144 steps to its first repeated point; √n ≈ 100.2
Measured over 1,000 walks each
Pollard's original walk 1.629√n, a 20-adding walk 1.291√n; a random function would take 1.2533√n

The instance

The curve is y2 = x3 + 3x + 6 over F10007. It has 10,039 points, and since that number is prime every point other than O generates the whole group, so there is no smaller subgroup for Pohlig–Hellman to exploit. Rho is the right tool, and for a random walk on 10,039 points the birthday bound predicts a repeat after about √(πn/2) ≈ 126 steps.

Take P = (0, 1973). The code that builds this page picks a secret k at random and publishes Q = kP = (2153, 30). The walk below never sees k; it only adds points and compares them.

The walk

Each point the walk visits is written as a known combination Xi = aiP + biQ. Pollard's original rule looks at the x-coordinate modulo 3 and makes one of three moves, updating the coefficients to match:

  • x ≡ 0: add P, so a increases by 1;
  • x ≡ 1: double, so a and b both double;
  • x ≡ 2: add Q, so b increases by 1.

The rule depends only on the current point, so once the walk reaches a point it has seen before, it repeats everything that followed. Start from random a0 and b0:

The walk from X0, with the rows around the repeat. Each row's last column is the step that produced the next row.
iXiaibix mod 3next step
0(3898, 7655)316967201double
1(5583, 7683)633834010add P
2(6314, 4213)633934012add Q
3(7052, 4713)633934022add Q
4(9108, 4303)633934030add P
5(4475, 6219)634034032add Q
…
94(833, 2456)657883412add Q
95(7310, 7583)657883422add Q
96(236, 7493)657883432add Q
…
143(9285, 2936)426513360add P
144(7310, 7583)426613362repeats X95

The repeat

At step 144 the walk returns to (7310, 7583), which it first reached at step 95. That one point now has two representations:

6578P + 8342Q = 4266P + 1336Q  ⇒  (8342 − 1336)Q = (4266 − 6578)P Subtracting the two representations of X95 = X144.
k ≡ 7727 · 7006−1 ≡ 7727 · 2168 ≡ 7084   (mod 10039) Dividing is possible because n is prime and b95 ≠ b144. The build checks that 7084P = Q.
X₀first repeated pointcycle: 49 stepstail: 95 steps
The walk drawn to scale: a tail of 95 points, then a cycle of 49. X95 is where the tail joins the cycle, and the only point the walk reaches twice.

This walk took 144 steps, 1.44√n, against the 126 the birthday bound suggests. One walk is one sample; the next section measures the average.

Not storing the walk

The code behind this page keeps every visited point in a table, which is the clearest way to show where the repeat happens and costs nothing at this size. At 2128 steps it is impossible. Floyd's and Brent's cycle-finding methods detect the repeat while storing only a couple of points. Parallel implementations instead report only distinguished points, those whose x-coordinate starts with a fixed number of zero bits, to a central server: two walks that merge reach the same distinguished point, the server sees it twice, and the logarithm follows exactly as above. That is the van Oorschot–Wiener method described on the attack page.

How long walks take

The 126-step prediction assumes the walk behaves like a random function. Whether it does is a property of the rule, and it can be measured. For each of two rules the code ran 1,000 walks, each with a fresh random target and starting point, and counted the steps until the first repeated point.

Steps until the first repeated point, divided by √n, over 1,000 random targets and starting points for each walk.
WalkMeanStandard error
Random function (prediction)1.253—
20-adding walk (Brent–Pollard prediction)1.286—
Teske, r = 20 additions1.2910.022
Pollard's original (add P, double, add Q)1.6290.026

Pollard's original rule is measurably worse than random: its walks run 30% longer. Teske identified the problem and proposed r-adding walks, which add one of r fixed random combinations of P and Q chosen by the current point. With r = 20 the measured mean is 1.291, +3.0% from the random-function value. A heuristic due to Brent and Pollard says an r-adding walk should be slower than random by a factor of 1/√(1 − 1/r), 2.6% for r = 20, and the measurement agrees with it to within its standard error.

This ratio, operations divided by √n, is the number our discrete-log library reports for every solver, so that different algorithms and implementations can be compared directly.

At real sizes

Nothing in the walk changes for a 256-bit curve except the numbers. The rule, the coefficients and the final division are the same. What changes is that √(πn/4) is about 2127.8, which no computation will reach; the table of standard curves is in the note on the ECDLP. In the other direction, a 60-bit group needs only about 230 steps, well within one computer's reach, and the public records sit between those extremes, near 114 bits.

Primary sources

  1. J. M. Pollard, "Monte Carlo methods for index computation (mod p)", Mathematics of Computation 32 (1978)
  2. E. Teske, "On random walks for Pollard's rho method", Mathematics of Computation 70 (2001)
  3. D. J. Bernstein, T. Lange and P. Schwabe, "On the correct use of the negation map in the Pollard rho method", PKC 2011
  4. P. C. van Oorschot and M. J. Wiener, "Parallel collision search with cryptanalytic applications", Journal of Cryptology 12 (1999)