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

THEOREM 4.34
Let p be an odd prim e. D efine the polynom ial

( p − 1) / 2
i

2

( p − 1) / 2

T i . H p ( T )=

i =0

Theellipticcurve E given by y 2 = x ( x − 1)( x − λ ) with λ ∈ F p is supersingular

ifand onlyif H p ( λ )=0 .

PROOF Since F p = ∪ n≥ 1 F p n ,wehave λ ∈ F q = F p n for some n .So E is
defined over F q . To determine supersingularity, it su ces to count points in
E ( F q ), by Proposition 4.31. We know (Exercise 4.4) that
x
F q

= x ( q− 1) / 2

in F q . Therefore, by Theorem 4.14,
# E ( F q )= q +1+
x

( x ( x − 1)( x − λ )) ( q− 1) / 2 ,

∈ F q

wherethisisnowanequalityin F q . The integers in this formula are regarded
as elements of F p ⊆ F q . The following lemma allows us to simplify the sum.

LEMMA 4.35
Let i> 0 be an integer. T hen

x i = 0

if q − 1 i

− 1

if q − 1 |i.

x ∈ F q

PROOF If q − 1 |i then x i = 1 for all nonzero x ,sothesumequals q − 1,
which equals − 1in F q . The group F q is cyclic of order q − 1. Let g be a
generator. Then every nonzero element of F q canbewrittenintheform g j
with 0

≤ j ≤ q − 2. Therefore, if q − 1 i ,

x i =0+

q − 2 q − 2

( g i ) j = ( g i ) q− 1

− 1

x i = ( g j ) i = =0 ,

g i − 1

x ∈ F q

∈ F q

j =0 j =0

x

since g q− 1 =1.

Expand ( x ( x − 1)( x − λ )) ( q− 1) / 2 into a polynomial of degree 3( q − 1) / 2.
There is no constant term, so the only term x i with q − 1 |i is x q− 1 .Let A q

be the coe cient of x q− 1 . By the lemma,

λ )) ( q− 1) / 2 = ( x ( x − 1)( x − − A q ,

x ∈ F q