Elliptic Curves over Q - Elliptic Curves: Number Theory and Cryptography - page 240

Now let's consider q = p .Since p ≡ 1 (mod 4), there is a square root of − 1

mod p .Since p ≡ 1 (mod 8), there is a square root of − 2mod p . Therefore,

both 2 and 2 have square roots mod p . Hensel's lemma (see Appendix A)

implies that both 2 and

−

− 2 have square roots in the p -adics. Let

w = √ 2 . v = √ − u =0 , 2 ,

Then u, v, w is a p -adic point on C 1 ,p,p .
Finally, we need to consider q . From a more advanced standpoint,

we could say that the curve C 1 ,p,p is a curve of genus 1 and that Hasse's
theorem holds for such curves. If we use the estimates from Hasse's theorem,
then we immediately find that C 1 ,p,p has points mod q for all q (except maybe
for a few small q , since we are not looking at the points at infinity on C 1 ,p,p ).
However, we have only proved Hasse's theorem for elliptic curves, rather than
for arbitrary genus 1 curves. In the following, we'll use Hasse's theorem only
for elliptic curves and show that C 1 ,p,p has points mod q . Hensel's lemma
then will imply that there is a q -adic point.
Subtracting the two equations defining C 1 ,p,p allows us to put the equations
into a more convenient form:

=2 ,p, ∞

w 2 − v 2 =4 ,

2

− pv 2 =2 p. (8.15)

Suppose we have a solution ( u 0 ,v 0 ,w 0 )mod q . It is impossible for both u 0
and w 0 to be 0 mod q .
Suppose u 0 ≡ 0(mod q ). Then w 0 ≡ 0(mod q ). Also, v 0 ≡ 0(mod q ).
Let u =0. Since −pv 0 ≡ 2 p (mod q ), Hensel's lemma says that there exists
v pv 2 =2 p . Applying Hensel's lemma ≡ v 0 (mod q )inthe q -adics such that −

w 0 satisfying w 2 v 2 = 4. Therefore, we have again gives the existence of w ≡ −

found a q -adic point. Similarly, if w 0 ≡ 0(mod q ), there is a q -adic point.

Finally, suppose u 0 ≡ 0(mod q )and w 0 ≡ 0(mod q ). Choose any v ≡ v 0

(mod q ). Now use Hensel's lemma to find u, w . This yields a q -adic point.
It remains to show that there is a point mod q .Let n be a quadratic
nonresidue mod q . Then every element of F q is either of the form u 2 or nu 2 .
Consider the curve

C : w 2 − v 2 =4 ,

2

− pv 2 =2 p. n

Let N be the number of points mod q on C 1 ,p,p and let N be the number of
points mod q on C . (We are not counting points at infinity.)

LEMMA 8.29
N + N =2( q − 1) .

PROOF Let x ≡ 0(mod q ). Solving

w + v ≡ x, w − v ≡ 4 /x (mod q )