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

Since we are in characteristic 2, there is at most one point of order 2 (see
Proposition 3.1). In fact, (0 , 1) has order 2. Therefore, E ( F 4 ) is cyclic of
order 8. Any one of the four points containing ω or ω 2 is a generator. This
may be verified by direct calculation, or by observing that they do not lie in
the order 4 subgroup E ( F 2 ). Let φ 2 ( x, y )=( x 2 ,y 2 )betheFrobeniusmap.
It is easy to see that φ 2 permutes the elements of E ( F 4 ), and

E ( F 2 )= { ( x, y ) ∈ E ( F 4 ) | φ 2 ( x, y )=( x, y ) } .

In general, for any elliptic curve E defined over F q and any extension F of
F q , the Frobenius map φ q permutes the elem en ts of E ( F ) and is the identity
on the subgroup E ( F q ). See Lemma 4.5.

Two main restrictions on the groups E ( F q ) are given in the next two the-
orems.

THEOREM 4.1
Let E be an elliptic curve over the finitefie d F q .Then

E ( F q ) Z n Z n 1 ⊕ Z n 2

or

forsomeinteger n ≥ 1 ,orforsomeintegers n 1 ,n 2 ≥ 1 with n 1 dividing n 2 .

PROOF A basic result in group theory (see Appendix B) says that a finite
abelian group is isomorphic to a direct sum of cyclic groups

Z n 1 ⊕ Z n 2 ⊕···⊕ Z n r ,

with n i |n i +1 for i ≥ 1. Since, for each i , the group Z n i has n 1 elements of
order dividing n 1 , we find that E ( F q )has n 1 elements of order dividing n 1 .By
Theorem 3.2, there are at most n 1 such points (even if we allow coordinates
in the algebraic closure of F q ). Therefore r 2. This is the desired result

(the group is trivial if r =0;thiscaseiscoveredby n = 1 in the theorem).

≤

THEOREM 4.2 (Hasse)
Let E be an elliptic curve over the finitefie d F q .Thenthe order of E ( F q )
satisfi es

2 √ q.

| q +1 − # E ( F q ) |≤

The proof will be given in Section 4.2.
A natural question is what groups can actually occur as groups E ( F q ). The
answer is given in the following two results, which are proved in [130] and [93],
respectively.