<< стр. 2(всего 3)СОДЕРЖАНИЕ >>
4

1в€’a
П‡2 (a)в€’1 П‡2 (1 в€’ a) = П‡2 .
a
a=0,1 a=0,1

1
The map x в†’ 1 в€’ x gives a permutation of the set of x в€€ Fp , x = 0, 1.
Therefore, letting c = 1 в€’ 1/a, we obtain
1
в€’1 П‡2 (в€’c) = в€’П‡2 (в€’1),
П‡2 =
a
a=0,1 c=0,1

by Lemma 4.26. Since g (pв€’1)/2 в‰Ў в€’1 (mod p) (both have order 2 in the cyclic
group FГ— ), we have
p

1 = (В±1)2 = П‡2 (g (pв€’1)/4 )2 = П‡2 (g (pв€’1)/2 ) = П‡2 (в€’1).

В© 2008 by Taylor & Francis Group, LLC
119
SECTION 4.4 A FAMILY OF CURVES

This yields the п¬Ѓrst equality of the proposition.
To prove the second equality, multiply the Jacobi sum by its complex con-
jugate to obtain

|J(П‡2 , П‡4 )|2 = П‡2 (a)П‡4 (1 в€’ a) П‡2 (b)П‡4 (1 в€’ b)
a=0,1 b=0,1

1в€’a
a
= П‡2 П‡4 .
1в€’b
b
a=0,1 b=0,1

We have used the fact that П‡4 (x) = П‡4 (x)в€’1 . We now need the following.

LEMMA 4.28
Let S = {(x, y) | x, y в€€ FГ— ; x, y = 1; x = y}. The map
p

x 1в€’x
Пѓ : (x, y) в†’ ,
y 1в€’y
is a permutation of S.

PROOF Let c = x/y and d = (1 в€’ x)/(1 в€’ y). Then x = 0 yields c = 0
and x = 1 yields d = 0. The assumption that x = y yields c, d = 1 and c = d.
Therefore, (c, d) в€€ S.
To show that Пѓ is surjective, let c, d в€€ S. Let
dв€’1
dв€’1
, y= .
x=c
dв€’c dв€’c
It is easily veriп¬Ѓed that (c, d) в€€ S implies (x, y) в€€ S and that Пѓ(x, y) = (c, d).

Returning to the proof of the proposition, we п¬Ѓnd that
1в€’a 1в€’a
a a
|J(П‡2 , П‡4 )|2 = П‡2 П‡4 + П‡2 П‡4
1в€’b 1в€’b
b b
(a,b)в€€S
a=b

= (p в€’ 2) + П‡2 (c)П‡4 (d)
(c,d)в€€S
вЋ› вЋћ

П‡4 (d) вЋќ П‡2 (c) в€’ П‡2 (1) в€’ П‡2 (d)вЋ
= (p в€’ 2) +
cв€€FГ—
d=0,1 p

П‡4 (d)(0 в€’ 1 в€’ П‡4 (d)2 )
= (p в€’ 2) +
d=0,1

П‡4 (d)3
= (p в€’ 2) в€’ П‡4 (d) в€’
d=0,1 d=0,1

= (p в€’ 2) + П‡4 (1) + П‡4 (1)3 = p.

В© 2008 by Taylor & Francis Group, LLC
120 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

This completes the proof of the second equality of Proposition 4.27.

We now show that the number of points on v 2 = (k/4)u4 + 1 can be ex-
pressed in terms of Jacobi sums. By separating out the terms with u = 0 and
the terms with v = 0, we obtain that the number of points is

#{v | v 2 = 1} + #{u | u4 = в€’4/k}

#{v | v 2 = a} #{u | u4 = в€’4b/k}
+
a+b=1
a,b=0

1 3 1 3
j j
= П‡2 (1) + П‡4 (в€’4/k) + П‡2 (a) П‡4 (в€’4b/k)
=0 =0
a+b=1
j=0 j=0
a,b=0

1 3 3
j
= П‡2 (1) + П‡4 (в€’4/k) + П‡4 (в€’4b/k)
=0 =0
j=0 b=0,1
1
П‡2 (a)j в€’ (p в€’ 2)
+
a=0,1 j=0

+П‡4 (в€’4/k)2 J(П‡2 , П‡2 ) + П‡4 (в€’4/k)J(П‡2 , П‡4 ) + П‡4 (в€’4/k)3 J(П‡2 , П‡3 )
4 4

(Separate out the terms with j = 0 and = 0. These yield the sums over
and over j, respectively. The terms with j = = 0, which sum to p в€’ 2, are
counted twice, so subtract p в€’ 2. The terms with j, = 0 contribute to the
Jacobi sums.)
1 3
П‡4 (в€’4b/k) в€’ (p в€’ 2)
j
П‡2 (a) +
=
=0 b=0
j=0 a=0

в€’П‡2 (в€’4/k) + П‡4 (в€’4/k)J(П‡2 , П‡4 ) + П‡4 (в€’4/k)3 J(П‡2 , П‡3 )
4

= (p в€’ 1) + (p в€’ 1) в€’ (p в€’ 2)
в€’П‡2 (в€’4/k) + П‡4 (в€’4/k)J(П‡2 , П‡4 ) + П‡4 (в€’4/k)3 J(П‡2 , П‡3 )
4
(by Lemma 4.26)

= p + 1 в€’ Оґ + П‡4 (в€’4/k)J(П‡2 , П‡4 ) + П‡4 (в€’4/k)3 J(П‡2 , П‡3 ).
4

For the last equality, we used the fact that

0 if k is not a square
1 + П‡2 (в€’4/k) = 1 + П‡2 (1/k) =
2 if k is a square mod p,

В© 2008 by Taylor & Francis Group, LLC
121
SECTION 4.4 A FAMILY OF CURVES

hence 1 + П‡2 (в€’4/k) = Оґ. Therefore,
#E(Fp ) = #{(u, v) в€€ Fp Г— Fp | v 2 = (k/4)u4 + 1} + Оґ
= p + 1 в€’ О± в€’ О±,
where
О± = в€’П‡4 (в€’4/k)J(П‡2 , П‡4 ) в€€ Z[i].
If we write О± = a + bi, then О± + О± = 2a. Proposition 4.27 implies that
a2 + b2 = p, so we have almost proved Theorem 4.23. It remains to evaluate
a mod 4.
Let x1 + y1 i, x2 + y2 i в€€ Z[i]. We say that
x1 + y1 i в‰Ў x2 + y2 i (mod 2 + 2i)
if
(x1 в€’ x2 ) + (y1 в€’ y2 )i = (x3 + y3 i)(2 + 2i)
for some x3 +y3 i в€€ Z[i]. Clearly в€’2i в‰Ў 2 (mod 2+2i). Since 2iв€’2 = i(2+2i)
and в€’2 = 2 + (в€’1 + i)(2 + 2i), we have
2i в‰Ў 2 в‰Ў в€’2 в‰Ў в€’2i (mod 2 + 2i).
It follows easily that
2П‡4 (a) в‰Ў 2 (mod 2 + 2i) (4.3)
for all a. Since p в€’ 1 is a multiple of 4 = (1 в€’ i)(2 + 2i), we have p в‰Ў 1
(mod 2 + 2i).

LEMMA 4.29
Let p в‰Ў 1 (mod 4) be prime. Then
J(П‡2 , П‡4 ) в‰Ў в€’1 (mod 2 + 2i).

Let S = {x в€€ FГ— | x = 1}. Let
PROOF p
x
П„ : S в†’ S, xв†’ .
xв€’1
It is easy to check that П„ (П„ (x)) = x for all x в€€ S and that x = 2 is the only
value of x such that П„ (x) = x. Put the elements of S, other than 2, into
pairs (x, П„ (x)). Note that if x is paired with y = П„ (x), then y is paired with
П„ (y) = П„ (П„ (x)) = x. This divides S into (p в€’ 3)/2 pairs plus the element 2,
which is not in a pair. We have

П‡2 (a)П‡4 (1 в€’ a) =
J(П‡2 , П‡4 ) =
a=0,1

a a
П‡2 (2)П‡4 (1 в€’ 2) + П‡2 (a)П‡4 (1 в€’ a) + П‡2 П‡4 1 в€’ ,
aв€’1 aв€’1
(a,П„ (a))

В© 2008 by Taylor & Francis Group, LLC
122 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

where the sum is over pairs (a, П„ (a)). Note that since П‡2 П‡4 = П‡в€’1 , we have
4

a a П‡2 (a) П‡4 (в€’1)
П‡4 1 в€’
П‡2 =
aв€’1 aв€’1 П‡2 (a в€’ 1) П‡4 (a в€’ 1)

= П‡2 (a)П‡4 (в€’1)П‡4 (a в€’ 1) = П‡2 (a)П‡4 (1 в€’ a).
Therefore, since П‡2 (2) = П‡4 (2)2 = П‡4 (4),

П‡2 (a)П‡4 (1 в€’ a)
J(П‡2 , П‡4 ) = П‡4 (в€’4) + 2
(a,П„ (a))

в‰Ў П‡4 (в€’4) + 2 (by (4.3))
(a,П„ (a))

в‰Ў П‡4 (в€’4) + (p в€’ 3) в‰Ў П‡4 (в€’4) в€’ 2 (mod 2 + 2i).

Suppose p в‰Ў 1 (mod 8). Since g (pв€’1)/2 в‰Ў в€’1 (mod p), we have that в€’1 is a
fourth power. It is well known that 2 is a square mod p if and only if p в‰Ў В±1
(mod 8) (this is one of the supplementary laws for quadratic reciprocity and
is covered in most elementary number theory texts). Therefore 4 is a fourth
power when p в‰Ў 1 (mod 8). It follows that П‡4 (в€’4) = 1.
Now suppose p в‰Ў 5 (mod 8). Then 2 is not a square mod p, so 2 в‰Ў g j
(mod p) with j odd. Therefore

в€’4 в‰Ў g 2j+(pв€’1)/2 (mod p).

Since 2j в‰Ў 2 (mod 4) and (p в€’ 1)/2 в‰Ў 2 (mod 4), it follows that в€’4 is a
fourth power mod p. Therefore, П‡4 (в€’4) = 1.
In both cases, we obtain J(П‡2 , П‡4 ) в‰Ў П‡4 (в€’4) в€’ 2 в‰Ў в€’1 (mod 2 + 2i).

Since we just proved that П‡4 (в€’4) = 1, the lemma implies that

О± = в€’П‡4 (в€’4/k)J(П‡2 , П‡4 ) = в€’П‡4 (1/k)J(П‡2 , П‡4 ) в‰Ў П‡4 (k)3 (mod 2 + 2i).

LEMMA 4.30
Let О± = x + yi в€€ Z[i].
1. If О± в‰Ў 1 (mod 2 + 2i), then x is odd and x + y в‰Ў 1 (mod 4).
2. If О± в‰Ў в€’1 (mod 2 + 2i), then x is odd and x + y в‰Ў 3 (mod 4).
3. If О± в‰Ў В±i (mod 2 + 2i), then x is even.

PROOF Suppose О± в‰Ў 1 (mod 2 + 2i), so О± в€’ 1 = (u + iv)(2 + 2i) for some
u, v. Since (1 в€’ i)(2 + 2i) = 4, we have

(x + y в€’ 1) + (y + 1 в€’ x)i = (1 в€’ i)(О± в€’ 1) = 4u + 4vi.

В© 2008 by Taylor & Francis Group, LLC
123
SECTION 4.5 SCHOOFвЂ™S ALGORITHM

Therefore, x + y в‰Ў 1 (mod 4) and x в€’ y в‰Ў 1 (mod 4). It follows that y is
even. This proves (1). The proofs of (2) and (3) are similar.

If k is a fourth power mod p, then П‡4 (k) = 1, so О± в‰Ў 1 (mod 2 + 2i). The
lemma yields О± = a + bi with b even and a + b в‰Ў 1 (mod 4). This proves
part of part (2) of Theorem 4.23. The other parts are proved similarly. This
completes the proof of Theorem 4.23.

4.5 Schoof вЂ™s Algorithm
In 1985, Schoof  published an algorithm for computing the number
of points on elliptic curves over п¬Ѓnite п¬Ѓelds Fq that runs much faster than
existing algorithms, at least for very large q. In particular, it requires at
most a constant times log8 q bit operations, in contrast to the q 1/4 used in
Baby Step, Giant Step, for example. Subsequently, Atkin and Elkies reп¬Ѓned
and improved SchoofвЂ™s method (see Section 12.4). It has now been used
successfully when q has several hundred decimal digits. In the following, weвЂ™ll
give SchoofвЂ™s method. For details of the method of Atkins and Elkies, see 
and . For other methods for counting points, see  and .
Suppose E is an elliptic curve given by y 2 = x3 + Ax + B over Fq . We
know, by HasseвЂ™s theorem, that
в€љ
#E(Fq ) = q + 1 в€’ a, with |a| в‰¤ 2 q.

Let S = {2, 3, 5, 7, . . . , L} be a set of primes such that
в€љ
> 4 q.
в€€S

If we can determine a mod for each prime в€€ S, then we know a mod ,
and therefore a is uniquely determined.
Let be prime. For simplicity, we assume = p, where p is the characteristic
of Fq . We also assume that q is odd. We want to compute a (mod ).
If = 2, this is easy. If x3 + Ax + B has a root e в€€ Fq , then (e, 0) в€€ E
and (e, 0) в€€ E(Fq ), so E(Fq ) has even order. In this case, q + 1 в€’ a в‰Ў 0
(mod 2), so a is even. If x3 + Ax + B has no roots in Fq , then E(Fq ) has no
points of order 2, and a is odd. To determine whether x3 + Ax + B has a root
in Fq , we could try all the elements in Fq , but there is a faster way. Recall
(see Appendix C) that the roots of xq в€’ x are exactly the elements of Fq .
Therefore, x3 + Ax + B has a root in Fq if and only if it has a root in common
with xq в€’ x. The Euclidean algorithm, applied to polynomials, yields the gcd
of the two polynomials.

В© 2008 by Taylor & Francis Group, LLC
124 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

If q is very large, the polynomial xq has very large degree. Therefore, it is
more eп¬ѓcient to compute xq в‰Ў xq (mod x3 + Ax + B) by successive squaring
(cf. Section 2.2), and then use the result to compute

gcd(xq в€’ x, x3 + Ax + B) = gcd(xq в€’ x, x3 + Ax + B).

If the gcd is 1, then there is no common root and a is odd. If the gcd is not
1, then a is even. This п¬Ѓnishes the case = 2.
2
In the following, various expressions such as xq and xq will be used. They
will always be computed mod a polynomial in a manner similar to that just
done in the case = 2
In Section 3.2, we deп¬Ѓned the division polynomials П€n . When n is odd, П€n
is a polynomial in x and, for (x, y) в€€ E(Fq ), we have

(x, y) в€€ E[n] в‡ђв‡’ П€n (x) = 0.

These polynomials play a crucial role in SchoofвЂ™s algorithm.
Let П†q be the Frobenius endomorphism (not to be confused with the poly-
nomials П†n from Section 3.2, which are not used in this section), so

П†q (x, y) = (xq , y q ).

By Theorem 4.10,
П†2 в€’ aП†q + q = 0.
q

Let (x, y) be a point of order . Then
2 2
xq , y q + q(x, y) = a (xq , y q ) .

Let
q в‰Ўq |q | < /2.
(mod ),
Then q(x, y) = q (x, y), so
2 2
xq , y q + q (x, y) = a (xq , y q ) .

Since (xq , y q ) is also a point of order , this relation determines a mod . The
idea is to compute all the terms except a in this relation, then determine a
value of a that makes the relation hold. Note that if the relation holds for
one point (x, y) в€€ E[ ], then we have determined a (mod ); hence, it holds
for all (x, y) в€€ E[ ].
2 2
= В±q (x, y) for some (x, y) в€€ E[ ]. Then
Assume п¬Ѓrst that xq , y q

def 2 2
+ q (x, y) = в€ћ,
xq , y q
(x , y ) =

В© 2008 by Taylor & Francis Group, LLC
125
SECTION 4.5 SCHOOFвЂ™S ALGORITHM

2 2
so a в‰Ў 0 (mod ). In this case, the x-coordinates of xq , y q and q (x, y) are
distinct, so the sum of the two points is found by the formula using the line
through the two points, rather than a tangent line or a vertical line. Write

j(x, y) = (xj , yj )

for integers j. We may compute xj and yj using division polynomials, as in
Section 3.2. Moreover, xj = r1,j (x) and yj = r2,j (x)y, as on page 47. We
have
2
2
y q в€’ yq 2
в€’ xq в€’ xq .
x= 2
xq в€’ xq
Writing
2 2
2 2
= y2 yq в€’1
y q в€’ yq в€’ r2,q (x)
2
2
= (x3 + Ax + B) (x3 + Ax + B)(q в€’1)/2
в€’ r2,q (x) ,

and noting that xq is a function of x, we change x into a rational function
of x. We want to п¬Ѓnd j such that

(x , y ) = (xq , yj ).
q
j

First, we look at the x-coordinates. Starting with (x, y) в€€ E[ ], we have
(x , y ) = В±(xq , yj ) if and only if x = xq . As pointed out above, if this
q
j j
happens for one point in E[ ], it happens for all (п¬Ѓnite) points in E[ ]. Since
the roots of П€ are the x-coordinates of the points in E[ ], this implies that

x в€’ xq в‰Ў 0 (mod П€ ) (4.4)
j

(this means that the numerator of x в€’ xq is a multiple of П€ ). We are using
j
here the fact that the roots of П€ are simple (otherwise, we would obtain only
that П€ divides some power of x в€’xq ). This is proved by noting that there are
j
2
в€’ 1 distinct points of order , since is assumed not to be the characteristic
of Fq . There are ( 2 в€’ 1)/2 distinct x-coordinates of these points, and all of
them are roots of П€ , which has degree ( 2 в€’ 1)/2. Therefore, the roots of П€
must be simple.
Assume now that we have found j such that (4.4) holds. Then

(x , y ) = В±(xq , yj ) = (xq , В±yj ).
q q
j j

To determine the sign, we need to look at the y-coordinates. Both y /y and
q
yj /y can be written as functions of x. If
q
(y в€’ yj )/y в‰Ў 0 (mod П€ ),

then a в‰Ў j (mod ). Otherwise, a в‰Ў в€’j (mod ). Therefore, we have found
a (mod ).

В© 2008 by Taylor & Francis Group, LLC
126 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

2 2
It remains to consider the case where xq , y q = В±q(x, y) for all (x, y) в€€
E[ ]. If
2 2
П†2 (x, y) = xq , y q = q(x, y),
q

then
aП†q (x, y) = П†2 (x, y) + q(x, y) = 2q(x, y),
q

hence
a2 q(x, y) = a2 П†2 (x, y) = (2q)2 (x, y).
q

Therefore, a2 q в‰Ў 4q 2 (mod ), so q is a square mod . If q is not a square
mod , then we cannot be in this case. If q is a square mod , let w2 в‰Ў q
(mod ). We have

(П†q + w)(П†q в€’ w)(x, y) = (П†2 в€’ q)(x, y) = в€ћ
q

for all (x, y) в€€ E[ ]. Let P be any point in E[ ]. Then either (П†q в€’ w)P = в€ћ,
so П†q P = wP , or P = (П†q в€’ w)P is a п¬Ѓnite point with (П†q + w)P = в€ћ.
Therefore, in either case, there exists a point P в€€ E[ ] with П†q P = В±wP .
Suppose there exists a point P в€€ E[ ] such that П†q P = wP . Then

в€ћ = (П†2 в€’ aП†q + q)P = (q в€’ aw + q)P,
q

so aw в‰Ў 2q в‰Ў 2w2 (mod ). Therefore, a в‰Ў 2w (mod ). Similarly, if there
exists P such that П†q P = в€’wP , then a в‰Ў в€’2w (mod ). We can check
whether we are in this case as follows. We need to know whether or not

(xq , y q ) = В±w(x, y) = В±(xw , yw ) = (xw , В±yw )

for some (x, y) в€€ E[ ]. Therefore, we compute xq в€’ xw , which is a rational
function of x. If
gcd(numerator(xq в€’ xw ), П€ ) = 1,
then there is some (x, y) в€€ E[ ] such that П†q (x, y) = В±w(x, y). If this happens,
then use the y-coordinates to determine the sign.
Why do we use the gcd rather than simply checking whether we have 0 mod
П€ ? The gcd checks for the existence of one point. Looking for 0 (mod П€ )
checks if the relation holds for all points simultaneously. The problem is that
we are not guaranteed that П†q P = В±wP for all P в€€ E[ ]. For example,
the matrix representing П†q on E[ ] might not be diagonalizable. It might
w1
be . In this case, the eigenvectors for П†q form a one-dimensional
0w
subspace.
If we have gcd(numerator(xq в€’ xw ), П€ ) = 1, then we cannot be in the case
2 2 2 2
xq , y q = q(x, y), so the only remaining case is xq , y q = в€’q(x, y). In
this case, aP = (П†2 + q)P = в€ћ for all P в€€ E[ ]. Therefore, a в‰Ў 0 (mod ).
q
We summarize SchoofвЂ™s algorithm as follows. We start with an elliptic curve
E over Fq given by y 2 = x3 +Ax+B. We want to compute #E(Fq ) = q+1в€’a.

В© 2008 by Taylor & Francis Group, LLC
127
SECTION 4.5 SCHOOFвЂ™S ALGORITHM

1. Choose a set of primes S = {2, 3, 5, . . . , L} (with p в€€ S) such that
в€љ
в€€S > 4 q.

2. If = 2, we have a в‰Ў 0 (mod 2) if and only if gcd(x3 +Ax+B, xq в€’x) =
1.

в€€ S, do the following.
3. For each odd prime

(a) Let q в‰Ў q (mod ) with |q | < /2.
(b) Compute the x-coordinate x of
2 2
(x , y ) = xq , y q + q (x, y) mod П€ .

(c) For j = 1, 2, . . . , ( в€’ 1)/2, do the following.
i. Compute the x-coordinate xj of (xj , yj ) = j(x, y).
ii. If x в€’ xq в‰Ў 0 (mod П€ ), go to step (iii). If not, try the next
j
value of j (in step (c)). If all values 1 в‰¤ j в‰¤ ( в€’ 1)/2 have
been tried, go to step (d).
q
iii. Compute y and yj . If (y в€’ yj )/y в‰Ў 0 (mod П€ ), then a в‰Ў j
(mod ). If not, then a в‰Ў в€’j (mod ).
(d) If all values 1 в‰¤ j в‰¤ ( в€’ 1)/2 have been tried without success, let
w2 в‰Ў q (mod ). If w does not exist, then a в‰Ў 0 (mod ).
(e) If gcd(numerator(xq в€’ xw ), П€ ) = 1, then a в‰Ў 0 (mod ). Other-
wise, compute

gcd(numerator((y q в€’ yw )/y), П€ ).

If this gcd is not 1, then a в‰Ў 2w (mod ). Otherwise, a в‰Ў в€’2w
(mod ).

4. Use the knowledge of a (mod ) for each в€€ S to compute a (mod ).
Choose the value of a that satisп¬Ѓes this congruence and such that |a| в‰¤
в€љ
2 q. The number of points in E(Fq ) is q + 1 в€’ a.

Example 4.13
Let E be the elliptic curve y 2 = x3 + 2x + 1 mod 19. Then

#E(F19 ) = 19 + 1 в€’ a.

We want to determine a. WeвЂ™ll show that
вЋ§
вЋЁ1 (mod 2)
aв‰Ў 2 (mod 3)
3 (mod 5).

В© 2008 by Taylor & Francis Group, LLC
128 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

Putting these together yields

a в‰Ў 23 (mod 30).
в€љ
Since |a| < 2 19 < 9, we must have a = в€’7.

x19 в‰Ў x2 + 13x + 14 (mod x3 + 2x + 1)

by successive squaring (cf. Section 2.2) and then use the result to compute

gcd(x19 в€’ x, x3 + 2x + 1) = gcd(x2 + 12x + 14, x3 + 2x + 1) = 1.

It follows that x3 + 2x + 1 has no roots in F19 . Therefore, there is no 2-torsion
in E(F19 ), so a в‰Ў 1 (mod 2).
For = 3, we proceed as in SchoofвЂ™s algorithm and eventually get to j = 1.
We have q 2 = 361 and we have q в‰Ў 1 (mod 3). Therefore, q = 1 and we need
to check whether
(x361 , y 361 ) + (x, y) = В±(x19 , y 19 )
for (x, y) в€€ E. The third division polynomial is

П€3 = 3x4 + 12x2 + 12x в€’ 4.

We compute the x-coordinate of (x361 , y 361 ) + (x, y):
2 2
y 361 в€’ y (x3 + 2x + 1)180 в€’ 1
361 3
в€’ x361 в€’ x,
в€’x в€’ x = (x + 2x + 1)
x361 в€’ x x361 в€’ x

where we have used the relation y 2 = x3 + 2x + 1. We need to reduce this
mod П€3 . The natural way to start is to use the extended Euclidean algorithm
to п¬Ѓnd the inverse of x361 в€’ x (mod П€3 ). However,

gcd(x361 в€’ x, П€3 ) = x в€’ 8 = 1,

so the multiplicative inverse does not exist. We could remove x в€’ 8 from the
numerator and denominator of
(x3 + 2x + 1)180 в€’ 1
,
x361 в€’ x
but this is unnecessary. Instead, we realize that since x = 8 is a root of П€3 ,
the point (8, 4) в€€ E(F19 ) has order 3. Therefore,

#E(F19 ) = 19 + 1 в€’ a в‰Ў 0 (mod 3),

so a в‰Ў 2 (mod 3).
For = 5, we follow SchoofвЂ™s algorithm, eventually arriving at j = 2. Note
that
19 в‰Ў 4 в‰Ў в€’1 (mod 5),

В© 2008 by Taylor & Francis Group, LLC
129
SECTION 4.5 SCHOOFвЂ™S ALGORITHM

so q = в€’1 and

19(x, y) = в€’(x, y) = (x, в€’y) for all (x, y) в€€ E.

We need to check whether

def def
?
(x , y ) = (x361 , y 361 ) + (x, в€’y) = В±2(x19 , y 19 ) = В±(x , y )

for all (x, y) в€€ E. The recurrence of Section 3.2 shows that the п¬Ѓfth division
polynomial is

П€5 = 32(x3 + 2x + 1)2 (x6 + 10x4 + 20x3 в€’ 20x2 в€’ 8x в€’ 8 в€’ 8) в€’ П€3
3

= 5x12 + 10x10 + 17x8 + 5x7 + x6 + 9x5 + 12x4 + 2x3 + 5x2 + 8x + 8.

The equation for the x-coordinates yields
2 2
y 361 + y 3x38 + 2
?
361
в€’ 2x19 = x
в€’x в€’xв‰Ў
x= (mod П€5 ).
x361 в€’ x 2y 19

When y 2 is changed to x3 + 2x + 1, this reduces to a polynomial relation in
x, which is then veriп¬Ѓed. Therefore,

a в‰Ў В±2 (mod 5).

To determine the sign, we look at the y-coordinates. The y-coordinate of
(x , y ) = (x361 , y 361 ) + (x, в€’y) is computed to be

y(9x11 + 13x10 + 15x9 + 15x7 + 18x6 + 17x5 + 8x4 + 12x3 + 8x + 6) (mod П€5 ).

The y-coordinate of (x , y ) = 2(x, y) is

y(13x10 + 15x9 + 16x8 + 13x7 + 8x6 + 6x5 + 17x4 + 18x3 + 8x + 18) (mod П€5 ).

A computation yields
19
)/y в‰Ў 0
(y + y (mod П€5 ).

This means that
19 19
(x , y ) в‰Ў (x , в€’y ) = в€’2(xq , y q ) (mod П€5 ).

It follows that a в‰Ў в€’2 (mod 5).
As we showed above, the information from = 2, 3, 5 is suп¬ѓcient to yield
a = в€’7. Therefore, #E(F19 ) = 27.

В© 2008 by Taylor & Francis Group, LLC
130 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

4.6 Supersingular Curves

An elliptic curve E in characteristic p is called supersingular if E[p] =
{в€ћ}. In other words, there are no points of order p, even with coordinates
in an algebraically closed п¬Ѓeld. Supersingular curves have many interesting
properties, some of which weвЂ™ll discuss in the present section.
Note: Supersingular curves are not singular curves in the sense of Sec-
tion 2.4. The term вЂњsingularвЂќ was used classically to describe the j-invariants
of elliptic curves with endomorphism rings larger than Z. These rings usually
are subrings of quadratic extensions of the rationals. The term вЂњsupersingu-
larвЂќ refers to j-invariants of curves with even larger rings of endomorphisms,
namely, subrings of quaternion algebras. These ideas will be discussed in
Chapter 10.
The following result is useful because it gives a simple way of determining
whether or not an elliptic curve over a п¬Ѓnite п¬Ѓeld is supersingular.

PROPOSITION 4.31
Let E be an elliptic curve over Fq , where q is a power of the prime number
p. Let a = q + 1 в€’ #E(Fq ). Then E is supersingular if and only if a в‰Ў 0
(mod p), which is if and only if #E(Fq ) в‰Ў 1 (mod p).

Write X 2 в€’ aX + q = (X в€’ О±)(X в€’ ОІ). Theorem 4.12 implies that
PROOF
#E(Fqn ) = q n + 1 в€’ (О±n + ОІ n ).
Lemma 4.13 says that sn = О±n + ОІ n satisп¬Ѓes the recurrence relation
sn+1 = asn в€’ qsnв€’1 .
s0 = 2, s1 = a,
Suppose a в‰Ў 0 (mod p). Then s1 = a в‰Ў 0 (mod p), and sn+1 в‰Ў 0 (mod p)
for all n в‰Ґ 1 by the recurrence. Therefore,
#E(Fqn ) = q n + 1 в€’ sn в‰Ў 1 (mod p),
so there are no points of order p in E(Fqn ) for any n в‰Ґ 1. Since Fq = в€Єnв‰Ґ1 Fqn ,
there are no points of order p in E(Fq ). Therefore, E is supersingular.
Now suppose a в‰Ў 0 (mod p). The recurrence implies that sn+1 в‰Ў asn
(mod p) for n в‰Ґ 1. Since s1 = a, we have sn в‰Ў an (mod p) for all n в‰Ґ 1.
Therefore
#E(Fqn ) = q n + 1 в€’ sn в‰Ў 1 в€’ an (mod p).
By FermatвЂ™s little theorem, apв€’1 в‰Ў 1 (mod p). Therefore, E(Fqpв€’1 ) has order
divisible by p, hence contains a point of order p. This means that E is not
supersingular.

В© 2008 by Taylor & Francis Group, LLC
131
SECTION 4.6 SUPERSINGULAR CURVES

For the last part of the proposition, note that

#E(Fq ) в‰Ў q + 1 в€’ a в‰Ў 1 в€’ a (mod p),

so #E(Fq ) в‰Ў 1 (mod p) if and only if a в‰Ў 0 (mod p).

COROLLARY 4.32
Suppose p в‰Ґ 5 is a prime and E is deп¬Ѓned over Fp . Then E is supersingular
if and only if a = 0, which is the case if and only if #E(Fp ) = p + 1.

PROOF If a = 0, then E is supersingular, by the proposition. Conversely,
suppose E is supersingular but a = 0. Then a в‰Ў 0 (mod p) implies that
в€љ в€љ
|a| в‰Ґ p. By HasseвЂ™s theorem, |a| в‰¤ 2 p, so we have p в‰¤ 2 p. This means
that p в‰¤ 4.

When p = 2 or p = 3, there are examples of supersingular curves with
a = 0. See Exercise 4.7.
For general п¬Ѓnite п¬Ѓelds Fq , it can be shown that if E deп¬Ѓned over Fq is
supersingular, then a2 is one of 0, q, 2q, 3q, 4q. See , , or Theorem 4.3.
In Section 3.1, we saw that the elliptic curve y 2 + a3 y = x3 + a4 x + a6
in characteristic 2 is supersingular. Also, in characteristic 3, the curve y 2 =
x3 + a2 x2 + a4 x + a6 is supersingular if and only if a2 = 0. Here is a way to
construct supersingular curves in many other characteristics.

PROPOSITION 4.33
Suppose q is odd and q в‰Ў 2 (mod 3). Let B в€€ FГ— . Then the elliptic curve E
q
given by y 2 = x3 + B is supersingular.

PROOF Let П€ : FГ— в†’ FГ— be the homomorphism deп¬Ѓned by П€(x) = x3 .
q q
Since q в€’ 1 is not a multiple of 3, there are no elements of order 3 in FГ— , so
q
the kernel of П€ is trivial. Therefore, П€ is injective, hence must be surjective
since it is a map from a п¬Ѓnite group to itself. In particular, every element of
Fq has a unique cube root in Fq .
For each y в€€ Fq , there is exactly one x в€€ Fq such that (x, y) lies on the
curve, namely, x is the unique cube root of y 2 в€’ B. Since there are q values
of y, we obtain q points. Including the point в€ћ yields

#E(Fq ) = q + 1.

Therefore, E is supersingular.

Later (Theorem 4.34), weвЂ™ll see how to obtain all supersingular elliptic
curves over an algebraically closed п¬Ѓeld.

В© 2008 by Taylor & Francis Group, LLC
132 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

An attractive feature of supersingular curves is that computations involving
an integer times a point can sometimes be done faster than might be expected.
Suppose E is a supersingular elliptic curve deп¬Ѓned over Fq and let P = (x, y)
be a point in E(Fqn ) for some n в‰Ґ 1. Usually n is large. Let k be a positive
integer. We want to compute kP . This can be done quickly by successive
doubling, but it is possible to do even better. LetвЂ™s assume that a = 0. Then

П†2 + q = 0
q

by Theorem 4.10. Therefore
2 2
q(x, y) = в€’П†2 (x, y) = xq , в€’y q .
q

2 2
The calculations of xq and y q involve п¬Ѓnite п¬Ѓeld arithmetic, which is gener-
ally faster than elliptic curve calculations. Moreover, if x and y are expressed
2 2
in terms of a normal basis of Fqn over Fq , then xq and y q are computed by
shift operations (see Appendix C). The procedure is now as follows:

1. Expand k in base q:

k = k0 + k1 q + k2 q 2 + В· В· В· + kr q r ,

with 0 в‰¤ ki < q.

2. Compute ki P = (xi , yi ) for each i.
2i 2i
3. Compute q i ki P = (xq , (в€’1)i yi ).
q
i

4. Sum the points q i ki P for 0 в‰¤ i в‰¤ r.

The main savings is in step (3), where elliptic curve calculations are replaced
by п¬Ѓnite п¬Ѓeld computations.
We now show how to obtain all supersingular curves over Fq . Note that
supersingularity means that there are no points of order p with coordinates
in the algebraic closure; hence, it is really a property of an elliptic curve over
an algebraically closed п¬Ѓeld. If we have two elliptic curves E1 and E2 deп¬Ѓned
over a п¬Ѓeld such that E1 can be transformed into E2 by a change of variables
deп¬Ѓned over some extension п¬Ѓeld, then E1 is supersingular if and only if E2
is supersingular.
For example, in Proposition 4.33, the curve y1 = x3 + B can be changed
2
1
into y2 = x3 + 1 via x2 = x1 /B 1/3 , y2 = y1 /B 1/2 . Therefore, it would have
2
2
suп¬ѓced to prove the proposition for the curve y 2 = x3 + 1.
Recall (Section 2.5.1) that an elliptic curve E over an algebraically closed
п¬Ѓeld of characteristic not 2 can be put into the Legendre form y 2 = x(x в€’
1)(x в€’ О») with О» = 0, 1.

В© 2008 by Taylor & Francis Group, LLC
133
SECTION 4.6 SUPERSINGULAR CURVES

THEOREM 4.34
Let p be an odd prime. Deп¬Ѓne the polynomial
(pв€’1)/2 2
(p в€’ 1)/2
T i.
Hp (T ) =
i
i=0

The elliptic curve E given by y 2 = x(xв€’1)(xв€’О») with О» в€€ Fp is supersingular
if and only if Hp (О») = 0.

PROOF Since Fp = в€Єnв‰Ґ1 Fpn , we have О» в€€ Fq = Fpn for some n. So E is
deп¬Ѓned over Fq . To determine supersingularity, it suп¬ѓces to count points in
E(Fq ), by Proposition 4.31. We know (Exercise 4.4) that
x
= x(qв€’1)/2
Fq
in Fq . Therefore, by Theorem 4.14,
(qв€’1)/2
(x(x в€’ 1)(x в€’ О»))
#E(Fq ) = q + 1 + ,
xв€€Fq

where this is now an equality in Fq . The integers in this formula are regarded
as elements of Fp вЉ† Fq . The following lemma allows us to simplify the sum.

LEMMA 4.35
Let i > 0 be an integer. Then
if q в€’ 1 i
0
xi =
в€’1 if q в€’ 1|i.
xв€€Fq

PROOF If q в€’ 1|i then xi = 1 for all nonzero x, so the sum equals q в€’ 1,
which equals в€’1 in Fq . The group FГ— is cyclic of order q в€’ 1. Let g be a
q
generator. Then every nonzero element of Fq can be written in the form g j
with 0 в‰¤ j в‰¤ q в€’ 2. Therefore, if q в€’ 1 i,
qв€’2 qв€’2
(g i )qв€’1 в€’ 1
i i ji ij
x =0+ x= (g ) = (g ) = = 0,
gi в€’ 1
Г— j=0 j=0
xв€€Fq xв€€Fq

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 xi with q в€’ 1|i is xqв€’1 . Let Aq
be the coeп¬ѓcient of xqв€’1 . By the lemma,
(x(x в€’ 1)(x в€’ О»))(qв€’1)/2 = в€’Aq ,
xв€€Fq

В© 2008 by Taylor & Francis Group, LLC
134 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

since all the powers of x except for xqв€’1 sum to 0. Therefore,

#E(Fq ) = 1 в€’ Aq in Fq .

By Proposition 4.31, E is supersingular if and only if Aq = 0 in Fq . The
following lemma allows us to relate Aq to Ap .

LEMMA 4.36
Let f (x) = x3 + c2 x2 + c1 x + c0 be a cubic polynomial with coeп¬ѓcients in a
r
п¬Ѓeld of characteristic p. For each r в‰Ґ 1, let Apr be the coeп¬ѓcient of xp в€’1 in
r
f (x)(p в€’1)/2 . Then
2 rв€’1
Apr = A1+p+p +В·В·В·+p .
p

PROOF We have
r r
(f (x)(pв€’1)/2 )p = (x3(pв€’1)/2 + В· В· В· + Ap xpв€’1 + В· В· В· )p
r r r
= x3(pв€’1)p (pв€’1)
+ В· В· В· + Ap xp + В·В·В· .
/2
p

Therefore,
pr
(pr+1 в€’1)/2 (pr в€’1)/2 (pв€’1)/2
f (x) = f (x) f (x)
r r
= (x3(p в€’1)/2 в€’1
+ В· В· В· + Apr xp + В·В·В·)
r r r
В·(x3(pв€’1)p (pв€’1)
+ В· В· В· + Ap xp + В· В· В· ).
/2
p

r+1
To obtain the coeп¬ѓcient of xp в€’1 , choose indices i and j with i + j =
pr+1 в€’ 1, multiply the corresponding coeп¬ѓcients from the п¬Ѓrst and second
factors in the above product, and sum over all such pairs i, j. A term with
0 в‰¤ i в‰¤ 3(pr в€’ 1)/2 from the п¬Ѓrst factor requires a term with
3
pr+1 в€’ 1 в‰Ґ j в‰Ґ (pr+1 в€’ 1) в€’ (pr в€’ 1) > (p в€’ 2)pr
2
from the second factor. Since all of the exponents in the second factor are
multiples of pr , the only index j in this range that has a nonzero exponent
is j = (p в€’ 1)pr . The corresponding index i is pr в€’ 1. The product of the
coeп¬ѓcients yields r
Apr+1 = Apr Ap .
p

The formula of the lemma is trivially true for r = 1. It now follows by an
easy induction for all r.

From the lemma, we now see that E is supersingular if and only if Ap = 0.
This is signiп¬Ѓcant progress, since Ap depends on p but not on which power of
p is used to get q.

В© 2008 by Taylor & Francis Group, LLC
135
SECTION 4.6 SUPERSINGULAR CURVES

It remains to express Ap as a polynomial in О». The coeп¬ѓcient Ap of xpв€’1
in (x(x в€’ 1)(x в€’ О»))(pв€’1)/2 is the coeп¬ѓcient of x(pв€’1)/2 in

((x в€’ 1)(x в€’ О»))(pв€’1)/2 .

By the binomial theorem,
(p в€’ 1)/2 i
(x в€’ 1)(pв€’1)/2 = x (в€’1)(pв€’1)/2в€’i
i
i
(p в€’ 1)/2 (pв€’1)/2в€’j
(x в€’ О»)(pв€’1)/2 = (в€’О»)j .
x
j
j

The coeп¬ѓcient Ap of x(pв€’1)/2 in (x в€’ 1)(pв€’1)/2 (x в€’ О»)(pв€’1)/2 is
(pв€’1)/2 2
(p в€’ 1)/2
(pв€’1)/2
О»k = (в€’1)(pв€’1)/2 Hp (О»).
(в€’1)
k
k=0

Therefore, E is supersingular if and only if Hp (О») = 0. This completes the
proof of Theorem 4.34.

It is possible to use the method of the preceding proof to determine when
certain curves are supersingular.

PROPOSITION 4.37
Let p в‰Ґ 5 be prime. Then the elliptic curve y 2 = x3 + 1 over Fp is supersin-
gular if and only if p в‰Ў 2 (mod 3), and the elliptic curve y 2 = x3 + x over Fp
is supersingular if and only if p в‰Ў 3 (mod 4).

PROOF The coeп¬ѓcient of xpв€’1 in (x3 + 1)(pв€’1)/2 is 0 if p в‰Ў 2 (mod 3)
(since we only get exponents that are multiples of 3), and is (pв€’1)/2 в‰Ў
(pв€’1)/3
0 (mod p) when p в‰Ў 1 (mod 3) (since the binomial coeп¬ѓcient contains no
factors of p). Since the coeп¬ѓcient of xpв€’1 is zero mod p if and only if the
curve is supersingular, this proves the п¬Ѓrst part.
The coeп¬ѓcient of xpв€’1 in (x3 + x)(pв€’1)/2 is the coeп¬ѓcient of x(pв€’1)/2 in
(x2 + 1)(pв€’1)/2 . All exponents appearing in this last expression are even,
so x(pв€’1)/2 doesnвЂ™t appear when p в‰Ў 3 (mod 4). When p в‰Ў 1 (mod 4),
the coeп¬ѓcient is (pв€’1)/2 в‰Ў 0 (mod p). This proves the second part of the
(pв€’1)/4
proposition.

If E is an elliptic curve deп¬Ѓned over Z with complex multiplication (see
в€љ
Chapter 10) by a subring of Q( в€’d), and p is an odd prime number not
dividing d for which E (mod p) is an elliptic curve, then E (mod p) is super-
singular if and only if в€’d is not a square mod p. Therefore, for such an E,

В© 2008 by Taylor & Francis Group, LLC
136 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

the curve E (mod p) is supersingular for approximately half of the primes.
proposition, the curve y 2 = x3 + 1 has complex multiplication by
In the в€љ
Z[(1 + в€’3)/2], and в€’3 is a square mod p if and only if p в‰Ў 1 (mod 3). The
в€љ
curve y 2 = x3 + x has complex multiplication by Z[ в€’1], and в€’1 is a square
mod p if and only if p в‰Ў 1 (mod 4).
If E does not have complex multiplication, the set of primes for which E
(mod p) is supersingular is much more sparse. Elkies  proved in 1986
that, for each E, the set of such primes is inп¬Ѓnite. Wan , 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/ ln2в€’ (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 в€љ Lang and Trotter
by
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 .
We now change our viewpoint and п¬Ѓx p and count supersingular E over
Fp . This essentially amounts to counting distinct zeros of Hp (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 Hp (T ). It is easy to see that Hp (0) = 1.
For Hp (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)/2
pв€’1 (p в€’ 1)/2
= Hp (1),
=
(p в€’ 1)/2 в€’ k
(p в€’ 1)/2 k
k

(use the identity n = nв€’k ). Since
n pв€’1
contains no factors p, it is
(pв€’1)/2
k
nonzero mod p. Therefore, Hp (1) = 0.

PROPOSITION 4.38
Hp (T ) has (p в€’ 1)/2 distinct roots in Fp .

PROOF We claim that

4T (1 в€’ T )Hp (T ) + 4(1 в€’ 2T )Hp (T ) в€’ Hp (T ) в‰Ў 0 (mod p). (4.5)

k
. The coeп¬ѓcient of T k on the left side of (4.5) is
Write Hp (T ) = k bk T

4(k + 1)kbk+1 в€’ 4k(k в€’ 1)bk + 4(k + 1)bk+1 в€’ 8kbk в€’ bk
= 4(k + 1)2 bk+1 в€’ (2k + 1)2 bk .

В© 2008 by Taylor & Francis Group, LLC
137
SECTION 4.6 SUPERSINGULAR CURVES

Using the fact that
2
(p в€’ 1)/2
bk+1 =
k+1
2
((p в€’ 1)/2)!
=
(k + 1)!(((p в€’ 1)/2) в€’ k в€’ 1)!
2
((p в€’ 1)/2) в€’ k
= bk ,
k+1

we п¬Ѓnd that the coeп¬ѓcient of T k is
2
4 (((p в€’ 1)/2) в€’ k) в€’ (2k + 1)2 bk = p(p в€’ 2 в€’ 4k)bk в‰Ў 0 (mod p).

This proves the claim.
Suppose now that Hp (О») = 0 with О» в€€ Fp . Since Hp (0) = 0 and Hp (1) = 0,
we have О» = 0, 1. Write Hp (T ) = (T в€’О»)r G(T ) for some polynomial G(T ) with
G(О») = 0. Suppose r в‰Ґ 2. In (4.5), we have (T в€’ О»)rв€’1 dividing the last term
and the middle term, but only (T в€’ О»)rв€’2 divides the term 4T (1 в€’ T )Hp (T ).
Since the sum of the three terms is 0, this is impossible, so we must have
r = 1. Therefore, О» is a simple root. (Technical point: Since the degree of
Hp (T ) is less than p, we have r < p, so the п¬Ѓrst term of the derivative

Hp (T ) = r(r в€’ 1)(T в€’ О»)rв€’2 G(T ) + 2r(T в€’ О»)rв€’1 G (T ) + (T в€’ О»)r G (T )

does not disappear in characteristic p. Hence (T в€’ О»)rв€’1 does not divide the
п¬Ѓrst term of (4.5).)

REMARK 4.39 The diп¬Ђerential equation 4.5 is called a Picard-Fuchs
diп¬Ђerential equation. For a discussion of this equation in the study of
families of elliptic curves in characteristic 0, see . Once we know that
Hp (T ) satisп¬Ѓes this diп¬Ђerential equation, the simplicity of the roots follows
from a characteristic p version of the uniqueness theorem for second order
diп¬Ђerential equations. If О» is a multiple root of Hp (T ), then Hp (О») = Hp (О») =
0. Such a uniqueness theorem would say that Hp (T ) must be identically 0,
which is a contradiction. Note that we must avoid О» = 0, 1 because of the
coeп¬ѓcient T (1 в€’ T ) for Hp (T ).

COROLLARY 4.40
Let p в‰Ґ 5 be prime. The number of j в€€ Fp that occur as j-invariants of
supersingular elliptic curves is
p
+ p,
12
= 0, 1, 1, 2 if p в‰Ў 1, 5, 7, 11 (mod 12), respectively.
where p

В© 2008 by Taylor & Francis Group, LLC
138 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

The j-invariant of y 2 = x(x в€’ 1)(x в€’ О») is
PROOF
(О»2 в€’ О» + 1)3
28
О»2 (О» в€’ 1)2
(see Exercise 2.13), so the values of О» yielding a given j are roots of the
polynomial
Pj (О») = 28 (О»2 в€’ О» + 1)3 в€’ jО»2 (О» в€’ 1)2 .
The discriminant of this polynomial is 230 (jв€’1728)3 j 4 , which is nonzero unless
j = 0 or 1728. Therefore, there are 6 distinct values of О» в€€ Fp corresponding
to each value of j = 0, 1728. If one of these О»вЂ™s is a root of Hp (T ), then all
six must be roots, since the corresponding elliptic curves are all the same (up
to changes of variables), and therefore all or none are supersingular.
Since the degree of Hp (T ) is (p в€’ 1)/2, we expect approximately (p в€’ 1)/12
supersingular j-invariants, with corrections needed for the cases when at least
one of j = 0 or j = 1728 is supersingular.
When j = 0, the polynomial Pj (О») becomes 28 (О»2 в€’ О» + 1)3 , so there are
two values of О» that give j = 0. When j = 1728, the polynomial becomes
28 (О» в€’ 2)2 (О» в€’ 1 )2 (О» + 1)2 , so there are three values of О» yielding j = 1728.
2
A curve with j-invariant 0 can be put into the form y 2 = x3 + 1 over an
algebraically closed п¬Ѓeld. Theorem 4.34 therefore tells us that when p в‰Ў 2
(mod 3), the two О»вЂ™s yielding j = 0 are roots of Hp (T ). Similarly, when p в‰Ў 3
(mod 4), the three О» yielding j = 1728 are roots of Hp (T ).
Putting everything together, the total count of roots of Hp (T ) is
6 В· #{supersingular j = 0, 1728} + 2Оґ2(3) + 3Оґ3(4)
= deg Hp (T ) = (p в€’ 1)/2,
where Оґi(j) = 1 if p в‰Ў i (mod j) and = 0 otherwise.
Suppose that p в‰Ў 5 (mod 12). Then Оґ2(3) = 1 and Оґ3(4) = 0, so the number
of supersingular j = 0, 1728 is
pв€’1 1 p
в€’= .
12 3 12
Adding 1 for the case j = 0 yields the number given in the proposition. The
other cases of p (mod 12) are similar.

Example 4.14
When p = 23, we have
H23 (T ) = (T в€’ 3)(T в€’ 8)(T в€’ 21)(T в€’ 11)(T в€’ 13)(T в€’ 16)
В·(T в€’ 2)(T в€’ 12)(T + 1)(T 2 в€’ T + 1)
(this is a factorization over F23 ). The п¬Ѓrst 6 factors correspond to
О»в€’1
1 1 О»
{О», , 1 в€’ О», },
, ,
1в€’О» О»в€’1
О» О»

В© 2008 by Taylor & Francis Group, LLC
139
EXERCISES

with О» = 3, hence to the curve y 2 = x(x в€’ 1)(x в€’ 3). The next three factors
correspond to j = 1728, hence to the curve y 2 = x3 + x. The last factor
corresponds to j = 0, hence to y 2 = x3 + 1. Therefore, we have found the
three supersingular curves over F23 . Of course, over F23 , there are diп¬Ђerent
forms of these curves. For example, y 2 = x3 + 1 and y 2 = x3 + 2 are diп¬Ђerent
curves over F23 , but are the same over F23 .

Example 4.15
When p = 13,

H13 (T ) в‰Ў (T 2 + 4T + 9)(T 2 + 12T + 3)(T 2 + 7T + 1).
в€љ
The six roots correspond to one value of j. Since О» = в€’2 + 8 is a root of
the п¬Ѓrst factor, the corresponding elliptic curve is
в€љ
y 2 = x(x в€’ 1)(x + 2 в€’ 8).

в€љ
The appearance of a square root such as 8 is fairly common. It is possible
to show that a supersingular curve over a perfect п¬Ѓeld of characteristic p
must have its j-invariant in Fp2 (see [109, Theorem V.3.1]). Therefore, a
supersingular elliptic curve over Fq can always be transformed via a change
of variables (over Fq ) into a curve deп¬Ѓned over Fp2 .

Exercises
4.1 Let E be the elliptic curve y 2 = x3 + x + 1 (mod 5).

(a) Show that 3(0, 1) = (2, 1) on E.
(b) Show that (0, 1) generates E(F5 ). (Use the fact that E(F5 ) has
order 9 (see Example 4.1), plus the fact that the order of any
element of a group divides the order of the group.)

4.2 Let E be the elliptic curve y 2 + y = x3 over F2 . Show that

2n + 1 if n is odd
#E(F2n ) =
2n + 1 в€’ 2(в€’2)n/2 if n is even.

4.3 Let Fq be a п¬Ѓnite п¬Ѓeld with q odd. Since FГ— is cyclic of even order q в€’1,
q
half of the elements of FГ— are squares and half are nonsquares.
q

В© 2008 by Taylor & Francis Group, LLC
140 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

(a) Let u в€€ Fq . Show that

x+u
= 0.
Fq
xв€€Fq

(b) Let f (x) = (x в€’ r)2 (x в€’ s), where r, s в€€ Fq with q odd. Show that

rв€’s
f (x)
=в€’ .
Fq Fq
xв€€Fq

(Hint: If x = r, then (x в€’ r)2 (x в€’ s) is a square exactly when x в€’ s
is a square.)

4.4 Let x в€€ Fq with q odd. Show that

x
= x(qв€’1)/2
Fq

as elements of Fq . (Remark: Since the exponentiation on the right
can be done quickly, for example, by successive squaring (this is the
multiplicative version of the successive doubling in Section 2.2), this
shows that the generalized Legendre symbol can be calculated quickly.
Of course, the classical Legendre symbol can also be calculated quickly

4.5 Let p в‰Ў 1 (mod 4) be prime and let E be given by y 2 = x3 в€’ kx, where
k в‰Ў 0 (mod p).

(a) Use Theorem 4.23 to show that #E(Fp ) is a multiple of 4 when k
is a square mod p.
(b) Show that when k is a square mod p, then E(Fp ) contains 4 points
P satisfying 2P = в€ћ. Conclude again that #E(Fp ) is a multiple
of 4.
(c) Show that when k is not a square mod p, then E(Fp ) contains no
points of order 4.
(d) Let k be a square but not a fourth power mod p. Show that exactly
one of the curves y 2 = x3 в€’ x and y 2 = x3 в€’ kx has a point of order
4 deп¬Ѓned over Fp .

4.6 Let E be an elliptic curve over Fq and suppose

Zn вЉ• Zmn .
E(Fq )

(a) Use the techniques of the proof of Proposition 4.16 to show that
q = mn2 + kn + 1 for some integer k.

В© 2008 by Taylor & Francis Group, LLC
141
EXERCISES

в€љ
(b) Use HasseвЂ™s theorem in the form a2 в‰¤ 4q to show that |k| в‰¤ 2 m.
Therefore, if m is п¬Ѓxed, q occurs as the value of one of п¬Ѓnitely many
(c) The prime number theorem implies that the number of prime pow-
ers less than x is approximately x/ ln x. Use this to show that most
prime powers do not occur as values of the п¬Ѓnite list of polynomials
in (b).
в€љв€љ
(d) Use HasseвЂ™s theorem to show that mn в‰Ґ m( q в€’ 1).
(e) Show that if m в‰Ґ 17 and q is suп¬ѓciently large (q в‰Ґ 1122 suп¬ѓces),
в€љ
then E(Fq ) has a point of order greater than 4 q.
(f) Show that for most values of q, an elliptic curve over Fq has a point
в€љ
of order greater than 4 q.

4.7 (a) Let E be deп¬Ѓned by y 2 + y = x3 + x over F2 . Show that #E(F2 ) =
5.
(b) Let E be deп¬Ѓned by y 2 = x3 в€’x+2 over F3 . Show that #E(F3 ) = 1.
(c) Show that the curves in (a) and (b) are supersingular, but that, in
each case, a = p + 1 в€’ #E(Fp ) = 0. This shows that the restriction
to p в‰Ґ 5 is needed in Corollary 4.32.

4.8 Let p в‰Ґ 5 be prime. Use Theorem 4.23 to prove HasseвЂ™s theorem for the
 << стр. 2(всего 3)СОДЕРЖАНИЕ >>