Elliptic Curves over Finite Fields - Elliptic Curves: Number Theory and Cryptography - page 107

2 √ q .Toprove
the proposition, we use the following lemma, which puts a severe restriction
on a .

By Hasse's theorem, n 2 PROOF = q +1 − a ,with | a |≤

LEMMA 4.17
a ≡ 2(mod n ) .

PROOF Let p be the characteristic of F q .Then p n ; otherwise, there

would be p 2

points in E [ p ], which is impossible in characteristic p by Theo-

rem 3.2.
Since E [ n ] ⊆ E ( F q ), Corollary 3.11 implies that the n th roots of unity
are in F q ,so q − 1 must be a multiple of n (see Appendix C). Therefore,

a = q +1 − n 2 ≡ 2(mod n ).

Write a =2+ kn for some integer k .Then

n 2 = q +1 q = n 2 + kn +1 . − a = q − 1 − kn, so

By Hasse's theorem,

| 2+ kn|≤ 2 √ q.

Squaring this last inequality yields

4+4 kn + k 2 n 2 4 q =4( n 2 + kn +1) .

≤

Therefore, |k|≤ 2. The possibilities k =0 , ± 1 , ± 2 give the values of q listed
in the proposition. This completes the proof of Proposition 4.16.

Most values of q are not of the form given in the proposition, and even
for such q most elliptic curves do not have E ( F q ) Z n ⊕ Z n (only a small
fraction have order n 2 ), so we can regard Z n ⊕ Z n as rare.
More generally, most q are such that all elliptic curves over F q have points

of order greater than 4 √ q (Exercise 4.6). Therefore, with a little luck, we can
usually find points with orders that allow us to determine # E ( F q ).
The following result of Mestre shows that for E defined over F p ,thereis
a point of su ciently high order on either E or its quadratic twist. The
quadratic twist of E is defined as follows. Let d ∈ F p be a quadratic non-
residue mod p .If E has equation y 2 = x 3 + Ax + B , then the quadratic twist
E has the equation y 2 = x 3 + Ad 2 x + Bd 3 (see Exercise 2.23). By Exercise
4.10, if # E ( F p )= p +1 − a then E has p +1+ a points. Once we know the
order of one of these two groups, we know a and therefore know the order of
both groups.