The Discrete Logarithm Problem - Elliptic Curves: Number Theory and Cryptography - page 146

Note that we did not need to know the exact order N of G .Weonly
required an upper bound for N . Therefore, for elliptic curves over F q ,we
could use this method with m 2 q +1+2 √ q , by Hasse's theorem.

A slight improvement of the method can be made for elliptic curves by
computing and storing only the points iP for 0

≥

≤ i ≤ m/ 2 and checking

whether Q − jmP = ±iP (see Exercise 5.1).

Example 5.2
Let G = E ( F 41 ), where E is given by y 2 = x 3 +2 x +1. Let P =(0 , 1) and
Q =(30 , 40). By Hasse's theorem, we know that the order of G is at most 54,
so we let m =8. Thepoints iP for 1 ≤ i ≤ 7are

(0 , 1) , (1 , 39) , (8 , 23) , (38 , 38) , (23 , 23) , (20 , 28) , (26 , 9) .

We calculate Q − jmP for j =0 , 1 , 2andobtain

(30 , 40) , (9 , 25) , (26 , 9) ,

at which point we stop since this third point matches 7 P .Since j = 2 yielded
thematch,wehave

(30 , 40) = (7 + 2 · 8) P =23 P.

Therefore k = 23.

5.2.2 Pollard's ρ and λ Methods

A disadvantage of the Baby Step, Giant Step method is that it requires a
lot of storage. Pollard's ρ and λ methods [87] run in approximately the same
time as Baby Step, Giant Step, but require very little storage. First, we'll
discuss the ρ method, then its generalization to the λ method.
Let G be a finite group of order N . Choose a function f : G → G that
behaves rather randomly. Then start with a random element P 0 and compute
the iterations P i +1 = f ( P i ). Since G is a finite set, there will be some indices
i 0 <j 0 such that P i 0 = P j 0 .Then

P i 0 +1 = f ( P i 0 )= f ( P j 0 )= P j 0 +1 ,

and, similarly, P i 0 + = P j 0 + for all 0. Therefore, the sequence P i is

periodic with period j 0 − i 0 (or possibly a divisor of j 0 − i 0 ). The picture
describing this process (see Figure 5.1) looks like the Greek letter ρ ,which
is why it is called Pollard's ρ method .If f is a randomly chosen random
function (we'll not make th is precise), then we expect to find a match with j 0

≥

at most a constant times √ N . For an analysis of the running time for various
choices of function f , see [119].