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

By the Cayley-Hamilton theorem of linear algebra, or by a straightforward
calculation (substituting the matrix into the polynomial), we have

( φ q ) 2 m −

a ( φ q ) m + qI ≡ 0(mod m ) ,

where I is the 2 × 2 identity matrix. (Note that X 2 −aX + q is the characteristic

polynomial of ( φ q ) m .) This means that the endomorphism φ q − aφ q + q is

identically zero on E [ m ]. Since there are infinitely many choices for m ,the
kernel of φ q − aφ q + q is infinite, so the endomorphism is 0.

= a satisfies φ q − Suppose a 1 a 1 φ q + q =0. Then

a 1 ) φ q =( φ q − ( φ q − ( a − a 1 φ q + q ) − aφ q + q )=0 .

By Theorem 2.2 2, φ q : E ( F q ) → E ( F q ) is surjective. Therefore, ( a − a 1 )

annihilates E ( F q ). In particular, ( a 1.

Since there are points in E [ m ]oforder m when gcd( m, q ) = 1, we find that
a

− a 1 ) annihilates E [ m ] for every m ≥

− a 1 ≡ 0(mod m )forsuch m . Therefore a − a 1 =0,so a is unique.

We single out the following result, which was proved during the proof of
Theorem 4.10.

PROPOSITION 4.11
Let E be an elliptic curve over F q and let ( φ q ) m denotethe m atrixgiving the
action of the Frobenius φ q on E [ m ] .Let a = q +1 − # E ( F q ) .Then

Trace(( φ q ) m ) ≡ a (mod m ) , det(( φ q ) m ) ≡ q (mod m ) .

The polynomial X 2 − aX + q is often called the characteristic polynomial

of Frobenius .

4.3 Determining the Group Order

Hasse's theorem gives bounds for the group of points on an elliptic curve
over a finite field. In this section and in Section 4.5, we'll discuss some methods
for actually determining the order of the group.

4.3.1 Subfield Curves

Sometimes we have an elliptic curve E defined over a small finite field F q
and we want to know the order of E ( F q n )forsome n . We can determine the