<<

. 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 [97] 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 [12]
and [99]. For other methods for counting points, see [60] and [94].
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[2]
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.
We start with = 2. We compute

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[3]. 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[5].

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[5]. 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 [98], [80], 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 [37] proved in 1986
that, for each E, the set of such primes is in¬nite. 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/ 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 [39].
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 [24]. 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
using quadratic reciprocity.)

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
quadratic polynomials.
(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)



>>