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

yields a pair ( v, w )foreach x .Thereare q − 1 choices for x , hence there are

1pairs( v, w ) satisfying w 2 v 2 =4. Let( v, w ) be such a pair. Consider q − −

the congruences

u 2 ≡ 2 p + pv 2 (mod q )and nu 2 ≡ 2 p + pv 2 (mod q ) .

If 2 p + pv 2

≡ 0(mod q ), then exactly one of these has a solution, and it has
2 solutions. If 2 p + pv 2 ≡ 0(mod q ), then both congruences have 1 solution.

Therefore, each of the q − 1pairs( v, w ) contributes 2 to the sum N + N ,so
N + N =2( q − 1).

The strategy now is the following. If N> 0, we're done. If N > 0,
then C can be transformed into an elliptic curve with approximately N
points. Hasse's theorem then gives a bound on N , which will show that
N =2( q − 1) − N > 0, so there must be points on C 1 ,p,p .

LEMMA 8.30
If q ≥ 11 ,then N> 0 .

PROOF If N =0then N =2( q− 1) > 0, by Lemma 8.29. In Section 2.5.4,
we showed how to start with the intersection of two quadratic surfaces and
a point and obtain an elliptic curve. Therefore, we can transform C t o

an elliptic curve E . By Hasse's theorem, E has less than q +1+2 √ q
points. We need to check that every point on C gives a point on E .Inthe
parameterization

w = 2+2 t 2
1 − t 2

4 t
1 − t 2 ,

v = (8.16)

of w 2 v 2 2). All of

the other points ( v, w ) correspond to finite values of t . No (finite) pair ( v, w )
corresponds to t = ± 1 (the lines through (0 , 2) of slope t = ± 1 are parallel to
the asymptotes of the hyperbola). Substituting the parameterization (8.16)
into nu 2

− = 4, the value t = ∞ corresponds to ( v, w )=(0 , −

− pv 2 =2 p yields the curve

u 1 = 2 p Q :

n ( t 4 +6 t 2 +1) ,

t 2 ) u .Apointon C where u 1 =(1 2) yields a finite

point on the quartic curve Q .Since C has 2( q − 1) > 1pointsmod q ,there
is at least one finite point on Q . Section 2.5.3 describes how to change Q
to an elliptic curve E (thecasewhere Q is singular does not occur since Q
is easily shown to be nonsingular mod q when q =2 ,p ). Every point mod q
on Q (including those at infinity, if they are defined over F q ) yields a point
(possibly ∞ )on E

− with ( v, w ) =(0 , −

(points at infinity on Q yield points of order 2 on E ).