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

PROOF Choose integers x 1 and x 2 such that x 1 ,x 2 (mod p )givethe x -
coordinates of P, Q . First, assume that x 1 ≡ x 2 (mod p ). Choose an integer

P =( x 1 ,y 1 ) reduces to P mod p .Nowchoose y 2 such that

y 1 such that

y 2 ≡ y 1 (mod x 2 − x 1 )and( x 2 ,y 2 ) ≡ Q (mod p ) .

This is possible by the Chinese Remainder Theorem, since gcd( p, x 2 − x 1 )=1

by assumption.
Consider the simultaneous equations

Ax 1 + B

y 1 = x 1 +

Ax 2 + B.

y 2 = x 2 +

A, B :

We can solve these for

y 2 − y 1 x 2 − x 1

A = B = y 1 − x 1 − Ax 1 .

x 1 − x 1 ,

x 2 − x 2 −

Since y 2 − y 1 is divisible by x 2 − x 1 , and since x 1 ,x 2 ,y 1 ,y 2 are integers, it

A , and therefore B , are integers. The points P and Q lie on the

follows that

curve E we obtain.
If x 1 ≡ x 2 (mod p ), then P = ±Q . In this case, take x 1 = x 2 .Then
choose y 1 that reduces mod p to the y -coordinate of P . Choose an integer
A ≡ A (mod p )andlet B = y 1 − x 1 − Ax 1 .Then P =( x 1 ,y 1 ) lies on E .Let

Q = P .Then Q reduces to

± ± P = Q mod p .

Finally, 4 A 3 +27 B 2

≡ 4 A 3 +27 B 2

≡ 0(mod p ), since E is an elliptic curve.

It follows that 4 A 3 +27 B 2

E is an elliptic curve.

= 0. Therefore

REMARK 5.7 If we start with Q = kP for some integer k ,itisvery
unlikely that this relation still holds on E . In fact, usually P and Q are
independent points. However, if they are dependent, so a P = b Q for some
nonzero integers a, b ,then aP = bQ , which allows us to find k (unless bP =
∞ ). The amazing thing about the case of anomalous curves is that even when

P and

Q are independent, we can extract enough information to find k .

Let a/b = 0 be a rational number, where a, b are relatively prime integers.
Write a/b = p r a 1 /b 1 with p a 1 b 1 . Define the p -adic valuation to be

v p ( a/b )= r.

For example,

v 2 (7 / 40) = − 3 , 5 (50 / 3) = 2 , 7 (1 / 2) = 0 .

Define v p (0) = + ∞ (so v p (0) >n for every integer n ).