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

E, P, Q , as in Proposition 5.6.

1. Lift E,P,Q to Z to obtain

E 1 since red p ( p P )=
p · red p ( P )= ∞ (thisiswhereweusethefactthat E is anomalous).

P 1 = p P, Q 1 = p Q . P 1 , Q 1 ∈

2. Let Note that

E 2 ,choosenew E, P, Q and try again. Otherwise, let 1 =
λ 1 ( P 1 )and 2 = λ 1 ( Q 1 ). We have k ≡ 2 / 1 (mod p ).
Whydoesthiswork? Let K = k P

P 1 ∈

3. If

Q .Wehave

−

∞ = kP − Q =red p ( k P −

Q )=red p ( K ) .

K ∈ E 1 ,so λ 1 ( K ) is defined and

Therefore

λ 1 ( p K )= pλ 1 ( K )

≡ 0(mod p ) .

Therefore,

2 = λ 1 ( k P 1 −

Q 1 )= λ 1 ( kp P

p Q )= λ 1 ( p K )

k 1 − − ≡ 0(mod p ) .

This means that k 2 / 1 (mod p ), as claimed.

Note that the assumption that E is anomalous is crucial. If E ( F p )has
order N , we need to multiply by N to put

≡

P, Q into E 1 ,where λ 1 is defined.

Q gets multiplied by N , also. When N is a multiple
of p ,wehave λ 1 ( N K ) ≡ 0(mod p ), so the contribution from

K = k P −

The difference

K disappears

from our calculations.
If we try to implement the above algorithm, we soon encounter di culties.
If p is a large prime, the point P 1 has coordinates whose numerators and
denominators are too large to work with. For example, the numerator and
denominator of the x -coordinate usually have approximately p 2 digits (see
Section 8.3). However, we are only looking for x/y (mod p ). As we shall see,
it su ces to work with numbers mod p 2 . (It is also possible to use the “dual
numbers” F p [ ], where 2 = 0; see [10].)
Let's try calculating on E (mod p 2 ). When we compute ( x, y )= P 1 = p P ,
we run into problems. Since

P 1 ∈ E 2 ,wehave p 2 in the denominator of x ,so

P 1 is already at

mod p 2 . Therefore, we cannot obtain information directly
from calculating λ 1 ( P 1 ). Instead, we calculate ( p

∞

1) P (mod p 2 ), then add

−

it to P , keeping track of p in denominators.
The procedure is the following.

E, P =( x 1 ,y 1 ) , Q =( x 2 ,y 2 ), as in Proposi-

1. Lift E,P,Q to Z to obtain

tion 5.6.

2. Calculate

P 2 =( p

1) P ( x ,y )(mod p 2 ) .

The rational numbers in the calculation of P 2 should not have p in their
denominators, so the denominators can be inverted mod p 2

− ≡

to obtain

integers x ,y .