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

E be an elliptic curve over Z given by y 2 = x 3 + Ax + B .Let r

Let ≥ 1be

an integer. Define

E r = E ( Q )

{ ( x, y ) ∈ | v p ( x ) ≤− 2 r, v p ( y ) ≤− 3 r }∪{∞} .

These are the points such that x has at least p 2 r in its denominator and y
has at least p 3 r in its denominator. These should be thought of as the points
that are close to ∞ mod powers of p (that is, p -adically close to ∞ ).

THEOREM 5.8
Let E be given by y 2 = x 3 +

Ax + B ,with A, B

∈ Z .Let p be primeand et

r be a positive integer. T hen

E r isasubgroupof E ( Q ) .

1.

E ( Q ) ,then v p ( x ) < 0 ifand onlyif v p ( y ) < 0 .Inthiscase,
there existsaninteger r ≥ 1 su ch that v p ( x )= − 2 r, v p ( y )= − 3 r .

2. If ( x, y ) ∈

3. T he m ap

E r / E 5 r → Z p 4 r
( x, y )

λ r :

p −r x/y (mod p 4 r )

→

∞ → 0

isaninjective hom om orphism (w here Z p 4 r is a group under addition).

E r but ( x, y ) ∈ E r +1 ,then λ r ( x, y ) ≡ 0(mod p ) .

4. If ( x, y ) ∈

This will be proved in Section 8.1. The map λ r should be regarded as a
logarithm for the group E r / E r +1 since it changes the law of composition in
the group to addition in Z p 4 r , just as the classical logarithm changes the com-
position law in the multiplicative group of positive real numbers to addition
in R .
We need one more fact, which is contained in Corollary 2.33: the reduction
mod p map

E ( Q ) E

red p : −→ (mod p )

E 1

( x, y ) → ( x, y )(mod p )w n x, y ) ∈

E 1 →{∞}

is a homomorphism. The kernel of red p is E 1 .
We are now ready for a theoretical version of the algorithm. We start with
an elliptic curve E over F p in Weierstrass form, and we have points P and
Q on E . We want to find an integer k such that Q = kP (assume k =0).
The crucial assumption is that E is anomalous, so # E ( F p )= p .Performthe
following steps.