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