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

the curve E (mod p ) is supersingular for approximately half of the primes.
In the p rop osition, the curve y 2 = x 3 + 1 has complex multiplication by

Z [(1 + √ − 3) / 2], and − 3isasquaremod p if and onl y if p ≡ 1(mod3).The

curve y 2 = x 3 + x has complex multiplication by Z [ √ − 1], and − 1isasquare

mod p if and only if p 1(mod4).

If E does not have complex multiplication, the set of primes for which E
(mod p ) is supersingular is much more sparse. Elkies [37] proved in 1986
that, for each E , the set of such primes is infinite. Wan [126], improving
on an argument of Serre, showed that, for each > 0, the number of such
p<x for which E (mod p ) is supersingular is less than C x/ ln 2 − ( x )for
some constant C depending on . Since the number of primes less than x
is approximately x/ ln x , this shows that substantially less than half of the
primes are supersingular for E . It has been conjectured b y Lang and Trotter

≡

that the number of supersingular p is asymptotic to C √ x/ ln x (as x →∞ )
for some constant C depending on E . This has been shown to be true “on
the average” by Fouvry and Murty [39].
We now change our viewpoint and fix p and count supersingular E over
F p . This essentially amounts to counting distinct zeros of H p ( T ). The values
λ =0 , 1 are not allowed in the Legendre form of an elliptic curve. Moreover,
they also don't appear as zeros of H p ( T ). It is easy to see that H p (0) = 1.
For H p (1), observe that the coe cient of x ( p− 1) / 2 in

( x +1) p− 1 =( x +1) ( p− 1) / 2 ( x +1) ( p− 1) / 2

is

p − 1
( p

=
k

( p − 1) / 2
k

( p − 1) / 2
( p

= H p (1) ,

− 1) / 2 − 1) / 2 − k

(use the identity k = n

k ). Since 1) / 2 contains no factors p ,itis

p − 1

n − ( p −

nonzero mod p . Therefore, H p (1) =0.

PROPOSITION 4.38
H p ( T ) has ( p − 1) / 2 distinctrootsin F p .

PROOF

We claim that

4 T (1 − T ) H p ( T )+4(1 − 2 T ) H p ( T ) − H p ( T ) ≡ 0(mod p ) . (4.5)

Write H p ( T )= k b k T k . The coecient of T k on the left side of (4.5) is

4( k +1) kb k +1 − 4 k ( k − 1) b k +4( k +1) b k +1 − 8 kb k − b k

=4( k +1) 2 b k +1 − (2 k +1) 2 b k .