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

order of E ( F q n )when n = 1 by listing the points or by some other elementary
procedure. The amazing fact is that this allows us to determine the order for
all n .

THEOREM 4.12
Let # E ( F q )= q +1

a .W rite X 2 − − aX + q =( X − α )( X − β ) .Then

# E ( F q n )= q n +1 ( α n + β n ) −

for all n

≥ 1 .

PROOF First, we need the fact that α n + β n is an integer. This could
be proved by remarking that it is an algebraic integer and is also a rational
number. However, it can also be proved by more elementary means.

LEMMA 4.13
Let s n = α n + β n .Then s 0 =2 , s 1 = a ,and s n +1 = as n −

qs n− 1 for all

n ≥ 1 .

Multiply the relation α 2 − aα + q =0by α n− 1 to obtain α n +1 = PROOF

aα n qα n− 1 . There is a similar relation for β . Add the two relations to

obtain the lemma.

−

It follows immediately from the lemma that α n + β n is an integer for all

n ≥ 0.
Let

f ( X )=( X n − α n )( X n − β n )= X 2 n − ( α n + β n ) X n + q n .

Then X 2

− aX + q =( X − α )( X − β ) divides f ( X ). It follows immediately
from the standard algorithm for dividing polynomials that the quotient is
a polynomial Q ( X ) with integer coecients (the main points are that the
leading coecient of X 2 − aX + q is 1 and that this polynomial and f ( X )

have integer coecients). Therefore

( φ q ) 2 − ( α n + β n ) φ q + q n = f ( φ q )= Q ( φ q )( φ q − aφ q + q )=0 ,

as endomorphisms of E , by Theorem 4.10. Note that φ q = φ q n .ByTheo-
rem 4.10, there is only one integer k such that φ q n − kφ q n + q n =0,andsuch
a k is determined by k = q n +1 − # E ( F q n ). Therefore,

α n + β n = q n +1 − # E ( F q n ) .

This completes the proof of Theorem 4.12.