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:
| i | Xi | ai | bi | x mod 3 | next step |
|---|---|---|---|---|---|
| 0 | (3898, 7655) | 3169 | 6720 | 1 | double |
| 1 | (5583, 7683) | 6338 | 3401 | 0 | add P |
| 2 | (6314, 4213) | 6339 | 3401 | 2 | add Q |
| 3 | (7052, 4713) | 6339 | 3402 | 2 | add Q |
| 4 | (9108, 4303) | 6339 | 3403 | 0 | add P |
| 5 | (4475, 6219) | 6340 | 3403 | 2 | add Q |
| … | |||||
| 94 | (833, 2456) | 6578 | 8341 | 2 | add Q |
| 95 | (7310, 7583) | 6578 | 8342 | 2 | add Q |
| 96 | (236, 7493) | 6578 | 8343 | 2 | add Q |
| … | |||||
| 143 | (9285, 2936) | 4265 | 1336 | 0 | add P |
| 144 | (7310, 7583) | 4266 | 1336 | 2 | repeats 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:
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.
| Walk | Mean | Standard error |
|---|---|---|
| Random function (prediction) | 1.253 | — |
| 20-adding walk (Brent–Pollard prediction) | 1.286 | — |
| Teske, r = 20 additions | 1.291 | 0.022 |
| Pollard's original (add P, double, add Q) | 1.629 | 0.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
- J. M. Pollard, "Monte Carlo methods for index computation (mod p)", Mathematics of Computation 32 (1978)
- E. Teske, "On random walks for Pollard's rho method", Mathematics of Computation 70 (2001)
- D. J. Bernstein, T. Lange and P. Schwabe, "On the correct use of the negation map in the Pollard rho method", PKC 2011
- P. C. van Oorschot and M. J. Wiener, "Parallel collision search with cryptanalytic applications", Journal of Cryptology 12 (1999)