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

P 59

P 6

P 58 P 5

P 4

P 3

P 2

P 1

P 0

Figure 5.1
Pollard's Rho Method

This gives us d choices for k . Usually, d will be small, so we can try all
possibilities until we have Q = kP .
In cryptographic applications, N is often prime, in which case, d =1or
N .If d = N , we have a trivial relation (the coe cients of both P and Q are
multiples of N ), so we start over. If d =1,weobtain k .

Example 5.3
Let G = E ( F 1093 ), where E is the elliptic curve given by y 2 = x 3 + x +1.
We'll use s =3. Let P =(0 , 1) and Q = (413 , 959). It can be shown that the
order of P is 1067. We want to find k such that kP = Q .Let

P 0 =3 P +5 Q, M 0 =4 P +3 Q, M 1 =9 P +17 Q, M 2 =19 P +6 Q.

Let f : E ( F 1093 ) → E ( F 1093 ) be defined by

f ( x, y )=( x, y )+ M i if x ≡ i (mod 3) .

Here the number x is regarded as an integer 0 ≤ x< 1093 and is then reduced
mod 3. For example,

f ( P 0 )= P 0 + M 2 = (727 , 589) ,

since P 0 = (326 , 69) and 326 ≡ 2(mod3).
We can define f ( ∞ )= ∞ if we want. However, if we encounter f ( ∞ ), we
have found a relation of the form aP + bQ = ∞ and can find k easily (if the
relation isn't something trivial like 1067 P +2134 Q = ∞ ). Therefore, we don't
worry about ∞ .