Elliptic Curves over Finite

Fields

Let F be a ¬nite ¬eld and let E be an elliptic curve de¬ned over F. Since

there are only ¬nitely many pairs (x, y) with x, y ∈ F, the group E(F) is

¬nite. Various properties of this group, for example, its order, turn out to

be important in many contexts. In this chapter, we present the basic theory

of elliptic curves over ¬nite ¬elds. Not only are the results interesting in

their own right, but also they are the starting points for the cryptographic

applications discussed in Chapter 6.

4.1 Examples

First, let™s consider some examples.

Example 4.1

Let E be the curve y 2 = x3 + x + 1 over F5 . To count points on E, we make a

list of the possible values of x, then of x3 + x + 1 (mod 5), then of the square

roots y of x3 + x + 1 (mod 5). This yields the points on E.

x x3 + x + 1 y Points

±1

0 1 (0, 1), (0, 4)

1 3 “ “

±1

2 1 (2, 1), (2, 4)

±1

3 1 (3, 1), (3, 4)

±2

4 4 (4, 2), (4, 3)

∞ ∞ ∞

Therefore, E(F5 ) has order 9.

95

© 2008 by Taylor & Francis Group, LLC

96 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

Let™s compute (3, 1) + (2, 4) on E. The slope of the line through the two

points is

4’1

≡ 2 (mod 5).

2’3

The line is therefore y = 2(x’3)+1 ≡ 2x. Substituting this into y 2 = x3 +x+1

and rearranging yields

0 = x3 ’ 4x2 + x + 1.

The sum of the roots is 4, and we know the roots 3 and 2. Therefore the

remaining root is x = 4. Since y = 2x, we have y ≡ 3. Re¬‚ecting across the

x-axis yields the sum:

(3, 1) + (2, 4) = (4, 2).

(Of course, we could have used the formulas of Section 2.2 directly.) A little

calculation shows that E(F5 ) is cyclic, generated by (0, 1) (Exercise 4.1).

Example 4.2

Let E be the elliptic curve y 2 = x3 + 2 over F7 . Then

E(F7 ) = {∞, (0, 3), (0, 4), (3, 1), (3, 6), (5, 1), (5, 6), (6, 1), (6, 6)}.

An easy calculation shows that all of these points P satisfy 3P = ∞, so the

group is isomorphic to Z3 • Z3 .

Example 4.3

Let™s consider the elliptic curve E given by y 2 + xy = x3 + 1 de¬ned over F2 .

We can ¬nd the points as before and obtain

E(F2 ) = {∞, (0, 1), (1, 0), (1, 1)}.

This is a cyclic group of order 4. The points (1, 0), (1, 1) have order 4 and the

point (0, 1) has order 2.

Now let™s look at E(F4 ). Recall that F4 is the ¬nite ¬eld with 4 elements.

We can write it as F4 = {0, 1, ω, ω 2 }, with the relation ω 2 + ω + 1 = 0 (which

implies, after multiplying by ω + 1, that ω 3 = 1). Let™s list the elements of

E(F4 ).

x = 0 ’ y2 = 1 ’ y = 1

x = 1 ’ y 2 + y = 0 ’ y = 0, 1

x = ω ’ y 2 + ωy = 0 ’ y = 0, ω

x = ω 2 ’ y 2 + ω 2 y = 0 ’ y = 0, ω 2

x = ∞ ’ y = ∞.

Therefore

E(F4 ) = ∞, (0, 1), (1, 0), (1, 1), (ω, 0), (ω, ω), (ω 2 , 0), (ω 2 , ω 2 ) .

© 2008 by Taylor & Francis Group, LLC

97

SECTION 4.1 EXAMPLES

Since we are in characteristic 2, there is at most one point of order 2 (see

Proposition 3.1). In fact, (0, 1) has order 2. Therefore, E(F4 ) is cyclic of

order 8. Any one of the four points containing ω or ω 2 is a generator. This

may be veri¬ed by direct calculation, or by observing that they do not lie in

the order 4 subgroup E(F2 ). Let φ2 (x, y) = (x2 , y 2 ) be the Frobenius map.

It is easy to see that φ2 permutes the elements of E(F4 ), and

E(F2 ) = {(x, y) ∈ E(F4 ) | φ2 (x, y) = (x, y) } .

In general, for any elliptic curve E de¬ned over Fq and any extension F of

Fq , the Frobenius map φq permutes the elements of E(F) and is the identity

on the subgroup E(Fq ). See Lemma 4.5.

Two main restrictions on the groups E(Fq ) are given in the next two the-

orems.

THEOREM 4.1

Let E be an elliptic curve over the ¬nite ¬eld Fq . Then

Zn1 • Zn2

E(Fq ) Zn or

for some integer n ≥ 1, or for some integers n1 , n2 ≥ 1 with n1 dividing n2 .

PROOF A basic result in group theory (see Appendix B) says that a ¬nite

abelian group is isomorphic to a direct sum of cyclic groups

Zn1 • Zn2 • · · · • Znr ,

with ni |ni+1 for i ≥ 1. Since, for each i, the group Zni has n1 elements of

order dividing n1 , we ¬nd that E(Fq ) has nr elements of order dividing n1 . By

1

Theorem 3.2, there are at most n2 such points (even if we allow coordinates

1

in the algebraic closure of Fq ). Therefore r ¤ 2. This is the desired result

(the group is trivial if r = 0; this case is covered by n = 1 in the theorem).

THEOREM 4.2 (Hasse)

Let E be an elliptic curve over the ¬nite ¬eld Fq . Then the order of E(Fq )

satis¬es

√

|q + 1 ’ #E(Fq )| ¤ 2 q.

The proof will be given in Section 4.2.

A natural question is what groups can actually occur as groups E(Fq ). The

answer is given in the following two results, which are proved in [130] and [93],

respectively.

© 2008 by Taylor & Francis Group, LLC

98 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

THEOREM 4.3

Let q = pn be a power of a prime p and let N = q + 1 ’ a. There is an elliptic

√

curve E de¬ned over Fq such that #E(Fq ) = N if and only if |a| ¤ 2 q and

a satis¬es one of the following:

1. gcd(a, p) = 1

√

2. n is even and a = ±2 q

√

3. n is even, p ≡ 1 (mod 3), and a = ± q

4. n is odd, p = 2 or 3, and a = ±p(n+1)/2

5. n is even, p ≡ 1 (mod 4), and a = 0

6. n is odd and a = 0.

THEOREM 4.4

Let N be an integer that occurs as the order of an elliptic curve over a ¬nite

¬eld Fq , as in Theorem 4.3. Write N = pe n1 n2 with p n1 n2 and n1 |n2

(possibly n1 = 1). There is an elliptic curve E over Fq such that

Zpe • Zn1 • Zn2

E(Fq )

if and only if

1. n1 |q ’ 1 in cases (1), (3), (4), (5), (6) of Theorem 4.3

2. n1 = n2 in case (2) of Theorem 4.3.

These are the only groups that occur as groups E(Fq ).

4.2 The Frobenius Endomorphism

Let Fq be a ¬nite ¬eld with algebraic closure Fq and let

φq : Fq ’’ Fq ,

x ’ xq

be the Frobenius map for Fq (see Appendix C for a review of ¬nite ¬elds).

Let E be an elliptic curve de¬ned over Fq . Then φq acts on the coordinates

of points in E(Fq ):

φq (∞) = ∞.

φq (x, y) = (xq , y q ),

© 2008 by Taylor & Francis Group, LLC

99

SECTION 4.2 THE FROBENIUS ENDOMORPHISM

LEMMA 4.5

Let E be de¬ned over Fq , and let (x, y) ∈ E(Fq ).

1. φq (x, y) ∈ E(Fq )

2. (x, y) ∈ E(Fq ) if and only if φq (x, y) = (x, y).

PROOF One fact we need is that (a + b)q = aq + bq when q is a power of

the characteristic of the ¬eld. We also need that aq = a for all a ∈ Fq . See

Appendix C.

Since the proof is the same for the Weierstrass and the generalized Weier-

strass equations, we work with the general form. We have

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,

with ai ∈ Fq . Raise the equation to the qth power to obtain

(y q )2 + a1 (xq y q ) + a3 (y q ) = (xq )3 + a2 (xq )2 + a4 (xq ) + a6 .

This means that (xq , y q ) lies on E, which proves (1).

For (2), again recall that x ∈ Fq if and only if φq (x) = x (see Appendix C),

and similarly for y. Therefore

(x, y) ∈ E(Fq ) ” x, y ∈ Fq

” φq (x) = x and φq (y) = y

” φq (x, y) = (x, y).

LEMMA 4.6

Let E be an elliptic curve de¬ned over Fq . Then φq is an endomorphism of

E of degree q, and φq is not separable.

This is the same as Lemma 2.20.

Note that the kernel of the endomorphism φq is trivial. This is related to

the fact that φq is not separable. See Proposition 2.21.

The following result is the key to counting points on elliptic curves over

¬nite ¬elds. Since φq is an endomorphism of E, so are φ2 = φq —¦ φq and also

q

φq = φq —¦ φq —¦ · · · —¦ φq for every n ≥ 1. Since multiplication by ’1 is also an

n

endomorphism, the sum φn ’ 1 is an endomorphism of E.

q

PROPOSITION 4.7

Let E be de¬ned over Fq and let n ≥ 1.

1. Ker(φn ’ 1) = E(Fqn ).

q

© 2008 by Taylor & Francis Group, LLC

100 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

2. φn ’ 1 is a separable endomorphism, so #E(Fqn ) = deg(φn ’ 1).

q q

PROOF Since φn is the Frobenius map for the ¬eld Fqn , part (1) is just

q

a restatement of Lemma 4.5. The fact that φn ’ 1 is separable was proved in

q

Proposition 2.29. Therefore (2) follows from Proposition 2.21.

Proof of Hasse™s theorem:

We can now prove Hasse™s theorem (Theorem 4.2). Let

a = q + 1 ’ #E(Fq ) = q + 1 ’ deg(φq ’ 1). (4.1)

√

We want to show that |a| ¤ 2 q. We need the following.

LEMMA 4.8

Let r, s be integers with gcd(s, q) = 1. Then deg(rφq ’ s) = r2 q + s2 ’ rsa.

PROOF Proposition 3.16 implies that

deg(rφq ’ s) = r2 deg(φq ) + s2 deg(’1) + rs(deg(φq ’ 1) ’ deg(φq ) ’ deg(’1)).

Since deg(φq ) = q and deg(’1) = 1, the result follows from (4.1).

REMARK 4.9 The assumption that gcd(s, q) = 1 is not needed. We

include it since we have proved Proposition 3.16 not in general, but only

when the endomorphisms are separable or φq .

We can now ¬nish the proof of Hasse™s theorem. Since deg(rφq ’ s) ≥ 0,

the lemma implies that

2

r r

’a +1≥0

q

s s

for all r, s with gcd(s, q) = 1. The set of rational numbers r/s such that

gcd(s, q) = 1 is dense in R. (Proof: Take s to be a power of 2 or a power of 3,

one of which must be relatively prime with q. The rationals of the form r/2m

and those of the form r/3m are easily seen to be dense in R.) Therefore,

qx2 ’ ax + 1 ≥ 0

for all real numbers x. Therefore the discriminant of the polynomial is negative

√

or 0, which means that a2 ’ 4q ¤ 0, hence |a| ¤ 2 q. This completes the

proof of Hasse™s theorem.

There are several major ingredients of the above proof. One is that we can

identify E(Fq ) as the kernel of φq ’ 1. Another is that φq ’ 1 is separable,

© 2008 by Taylor & Francis Group, LLC

101

SECTION 4.2 THE FROBENIUS ENDOMORPHISM

so the order of the kernel is the degree of φq ’ 1. A third major ingredient

is the Weil pairing, especially part (6) of Theorem 3.9, and its consequence,

Proposition 3.16.

Proposition 4.7 has another very useful consequence.

THEOREM 4.10

Let E be an elliptic curve de¬ned over Fq . Let a be as in Equation 4.1. Then

φ2 ’ aφq + q = 0

q

as endomorphisms of E, and a is the unique integer k such that

φ2 ’ kφq + q = 0.

q

In other words, if (x, y) ∈ E(Fq ), then

2 2

’ a (xq , y q ) + q(x, y) = ∞,

xq , y q

and a is the unique integer such that this relation holds for all (x, y) ∈ E(Fq ).

Moreover, a is the unique integer satisfying

a ≡ Trace((φq )m ) mod m

for all m with gcd(m, q) = 1.

PROOF If φ2 ’ aφq + q is not the zero endomorphism, then its kernel

q

is ¬nite (Proposition 2.21). We™ll show that the kernel is in¬nite, hence the

endomorphism is 0.

Let m ≥ 1 be an integer with gcd(m, q) = 1. Recall that φq induces a

matrix (φq )m that describes the action of φq on E[m]. Let

st

(φq )m = .

uv

Since φq ’1 is separable by Proposition 2.29, Propositions 2.21 and 3.15 imply

that

#Ker(φq ’ 1) = deg(φq ’ 1) ≡ det((φq )m ’ I)

= sv ’ tu ’ (s + v) + 1 (mod m).

By Proposition 3.15, sv’tu = det((φq )m ) ≡ q (mod m). By (4.1), #Ker(φq ’

1) = q + 1 ’ a. Therefore,

Trace((φq )m ) = s + v ≡ a (mod m).

© 2008 by Taylor & Francis Group, LLC

102 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

By the Cayley-Hamilton theorem of linear algebra, or by a straightforward

calculation (substituting the matrix into the polynomial), we have

(φq )2 ’ a(φq )m + qI ≡ 0 (mod m),

m

where I is the 2—2 identity matrix. (Note that X 2 ’aX +q is the characteristic

polynomial of (φq )m .) This means that the endomorphism φ2 ’ aφq + q is

q

identically zero on E[m]. Since there are in¬nitely many choices for m, the

kernel of φ2 ’ aφq + q is in¬nite, so the endomorphism is 0.

q

Suppose a1 = a satis¬es φ2 ’ a1 φq + q = 0. Then

q

(a ’ a1 )φq = (φ2 ’ a1 φq + q) ’ (φ2 ’ aφq + q) = 0.

q q

By Theorem 2.22, φq : E(Fq ) ’ E(Fq ) is surjective. Therefore, (a ’ a1 )

annihilates E(Fq ). In particular, (a ’ a1 ) annihilates E[m] for every m ≥ 1.

Since there are points in E[m] of order m when gcd(m, q) = 1, we ¬nd that

a ’ a1 ≡ 0 (mod m) for such m. Therefore a ’ a1 = 0, so a is unique.

We single out the following result, which was proved during the proof of

Theorem 4.10.

PROPOSITION 4.11

Let E be an elliptic curve over Fq and let (φq )m denote the matrix giving the

action of the Frobenius φq on E[m]. Let a = q + 1 ’ #E(Fq ). Then

Trace((φq )m ) ≡ a det((φq )m ) ≡ q

(mod m), (mod m).

The polynomial X 2 ’aX +q is often called the characteristic polynomial

of Frobenius.

4.3 Determining the Group Order

Hasse™s theorem gives bounds for the group of points on an elliptic curve

over a ¬nite ¬eld. In this section and in Section 4.5, we™ll discuss some methods

for actually determining the order of the group.

4.3.1 Sub¬eld Curves

Sometimes we have an elliptic curve E de¬ned over a small ¬nite ¬eld Fq

and we want to know the order of E(Fqn ) for some n. We can determine the

© 2008 by Taylor & Francis Group, LLC

103

SECTION 4.3 DETERMINING THE GROUP ORDER

order of E(Fqn ) when n = 1 by listing the points or by some other elementary

procedure. The amazing fact is that this allows us to determine the order for

all n.

THEOREM 4.12

Let #E(Fq ) = q + 1 ’ a. Write X 2 ’ aX + q = (X ’ ±)(X ’ β). Then

#E(Fqn ) = q n + 1 ’ (±n + β n )

for all n ≥ 1.

PROOF First, we need the fact that ±n + β n is an integer. This could

be proved by remarking that it is an algebraic integer and is also a rational

number. However, it can also be proved by more elementary means.

LEMMA 4.13

Let sn = ±n + β n . Then s0 = 2, s1 = a, and sn+1 = asn ’ qsn’1 for all

n ≥ 1.

PROOF Multiply the relation ±2 ’ a± + q = 0 by ±n’1 to obtain ±n+1 =

a±n ’ q±n’1 . There is a similar relation for β. Add the two relations to

obtain the lemma.

It follows immediately from the lemma that ±n + β n is an integer for all

n ≥ 0.

Let

f (X) = (X n ’ ±n )(X n ’ β n ) = X 2n ’ (±n + β n )X n + q n .

Then X 2 ’ aX + q = (X ’ ±)(X ’ β) divides f (X). It follows immediately

from the standard algorithm for dividing polynomials that the quotient is

a polynomial Q(X) with integer coe¬cients (the main points are that the

leading coe¬cient of X 2 ’ aX + q is 1 and that this polynomial and f (X)

have integer coe¬cients). Therefore

(φn )2 ’ (±n + β n )φn + q n = f (φq ) = Q(φq )(φ2 ’ aφq + q) = 0,

q q q

as endomorphisms of E, by Theorem 4.10. Note that φn = φqn . By Theo-

q

rem 4.10, there is only one integer k such that φ2n ’ kφqn + q n = 0, and such

q

a k is determined by k = q n + 1 ’ #E(Fqn ). Therefore,

±n + β n = q n + 1 ’ #E(Fqn ).

This completes the proof of Theorem 4.12.

© 2008 by Taylor & Francis Group, LLC

104 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

Example 4.4

In Example 4.3, we showed that the elliptic curve E given by y 2 +xy = x3 +1

over F2 satis¬es #E(F2 ) = 4. Therefore, a = 2 + 1 ’ 4 = ’1, and we obtain

the polynomial

√ √

’1 + ’7 ’1 ’ ’7

2

X +X +2= X ’ X’ .

2 2

Theorem 4.12 says that

√ √

2 2

’1 + ’7 ’1 ’ ’7

#E(F4 ) = 4 + 1 ’ ’ .

2 2

Rather than computing the last expression directly, we can use the recurrence

in Lemma 4.13:

s2 = as1 ’ 2s0 = ’(’1) ’ 2(2) = ’3.

It follows that #E(F4 ) = 4 + 1 ’ (’3) = 8, which is what we calculated by

listing points.

Similarly, using the recurrence or using su¬ciently high precision ¬‚oating

point arithmetic yields

√

√ 101 101

’1 + ’7 ’1 ’ ’7

+ = 2969292210605269.

2 2

Therefore,

#E(F2101 ) = 2101 + 1 ’ 2969292210605269

= 2535301200456455833701195805484.

The advantage of Theorem 4.12 is that it allows us to determine the group

order for certain curves very quickly. The disadvantage is that it requires the

curve to be de¬ned over a small ¬nite ¬eld.

4.3.2 Legendre Symbols

To make a list of points on y 2 = x3 + Ax + B over a ¬nite ¬eld, we tried

each possible value of x, then found the square roots y of x3 + Ax + B, if they

existed. This procedure is the basis for a simple point counting algorithm.

Recall the Legendre symbol x for an odd prime p, which is de¬ned as

p

follows:

§

⎨ +1 if t2 ≡ x (mod p) has a solution t ≡ 0 (mod p),

x

= ’1 if t2 ≡ x (mod p) has no solution t

©

p

0 if x ≡ 0 (mod p).

© 2008 by Taylor & Francis Group, LLC

105

SECTION 4.3 DETERMINING THE GROUP ORDER

This can be generalized to any ¬nite ¬eld Fq with q odd by de¬ning, for

x ∈ Fq ,

§

⎨ +1 if t2 = x has a solution t ∈ F— ,

q

x

= ’1 if t2 = x has no solution t ∈ Fq ,

©

Fq

0 if x = 0.

THEOREM 4.14

Let E be an elliptic curve de¬ned by y 2 = x3 + Ax + B over Fq . Then

x3 + Ax + B

#E(Fq ) = q + 1 + .

Fq

x∈Fq

PROOF For a given x0 , there are two points (x, y) with x-coordinate x0

if x3 + Ax0 + B is a nonzero square in Fq , one such point if it is zero, and no

0

points if it is not a square. Therefore, the number of points with x-coordinate

x3 +Ax +B

. Summing over all x0 ∈ Fq , and including 1 for

x0 equals 1 + 0 Fq0

the point ∞, yields

x3 + Ax + B

#E(Fq ) = 1 + 1+ .

Fq

x∈Fq

Collecting the term 1 from each of the q summands yields the desired formula.

COROLLARY 4.15

Let x3 + Ax + B be a polynomial with A, B ∈ Fq , where q is odd. Then

x3 + Ax + B √

¤ 2 q.

Fq

x∈Fq

PROOF When x3 + Ax + B has no repeated roots, y 2 = x3 + Ax + B gives

an elliptic curve, so Theorem 4.14 says that

x3 + Ax + B

q + 1 ’ #E(Fq ) = ’ .

Fq

x∈Fq

The result now follows from Hasse™s theorem.

The case where x3 + Ax + B has repeated roots follows from Exercise 4.3.

© 2008 by Taylor & Francis Group, LLC

106 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

Example 4.5

Let E be the curve y 2 = x3 + x + 1 over F5 , as in Example 4.1. The nonzero

squares mod 5 are 1 and 4. Therefore

4

x3 + x + 1

#E(F5 ) = 5 + 1 +

5

x=0

1 3 1 1 4

= 6+ + + + +

5 5 5 5 5

= 6 + 1 ’ 1 + 1 + 1 + 1 = 9.

When using Theorem 4.14, it is possible to compute each individual gen-

eralized Legendre symbol quickly (see Exercise 4.4), but it is more e¬cient

to square all the elements of F— and store the list of squares. For simplicity,

q

consider the case of Fp . Make a vector with p entries, one for each element

of Fp . Initially, all entries in the vector are set equal to ’1. For each j with

1 ¤ j ¤ (p ’ 1)/2, square j and reduce to get k mod p. Change the kth entry

in the vector to +1. Finally, change the 0th entry in the vector to 0. The

resulting vector will be a list of the values of the Legendre symbol.

Theorem 4.14, which is sometimes known as the Lang-Trotter method,

works quickly for small values of q, perhaps q < 100, but is slow for larger q,

and is impossible to use when q is around 10100 or larger.

4.3.3 Orders of Points

Let P ∈ E(Fq ). The order of P is the smallest positive integer k such that

kP = ∞. A fundamental result from group theory (a corollary of Lagrange™s

theorem) is that the order of a point always divides the order of the group

E(Fq ). Also, for an integer n, we have nP = ∞ if and only if the order of

√

P divides n. By Hasse™s theorem, #E(Fq ) lies in an interval of length 4 q.

√

Therefore, if we can ¬nd a point of order greater than 4 q, there can be only

one multiple of this order in the correct interval, and it must be #E(Fq ).

√

Even if the order of the point is smaller than 4 q, we obtain a small list

of possibilities for #E(Fq ). Using a few more points often shortens the list

enough that there is a unique possibility for #E(Fq ). For an addiitonal trick

that helps in this situation, see Proposition 4.18.

How do we ¬nd the order of a point? If we know the order of the full group

of points, then we can look at factors of this order. But, at present, the order

of the group is what we™re trying to ¬nd. In Section 4.3.4, we™ll discuss a

method (Baby Step, Giant Step) for ¬nding the order of a point.

© 2008 by Taylor & Francis Group, LLC

107

SECTION 4.3 DETERMINING THE GROUP ORDER

Example 4.6

Let E be the curve y 2 = x3 + 7x + 1 over F101 . It is possible to show that the

point (0, 1) has order 116, so N101 = #E(F101 ) is a multiple of 116. Hasse™s

theorem says that

√ √

101 + 1 ’ 2 101 ¤ N101 ¤ 101 + 1 + 2 101,

which means that 82 ¤ N101 ¤ 122. The only multiple of 116 in this range is

116, so N101 = 116. As a corollary, we ¬nd that the group of points is cyclic

of order 116, generated by (0,1).

Example 4.7

Let E be the elliptic curve y 2 = x3 ’ 10x + 21 over F557 . The point (2, 3) can

be shown to have order 189. Hasse™s theorem implies that 511 ¤ N557 ¤ 605.

The only multiple of 189 in this range is 3 · 189 = 567. Therefore N557 = 567.

Example 4.8

Let E be the elliptic curve y 2 = x3 + 7x + 12 over F103 . The point (’1, 2)

has order 13 and the point (19, 0) has order 2. Therefore the order N103 of

E(F103 ) is a multiple of 26. Hasse™s theorem implies that 84 ¤ N103 ¤ 124.

The only multiple of 26 in that range is 104, so N103 = 104.

Example 4.9

Let E be the elliptic curve y 2 = x3 + 2 over F7 , as in Example 4.2. The group

of points E(F7 ) is isomorphic to Z3 • Z3 . Every point, except ∞, has order

3, so the best we can conclude with the present method is that the order N7

of the group is a multiple of 3. Hasse™s theorem says that 3 ¤ N7 ¤ 13, so the

order is 3, 6, 9, or 12. Of course, if we ¬nd two independent points of order 3

(that is, one is not a multiple of the other), then they generate a subgroup of

order 9. This means that the order of the full group is a multiple of 9, hence

is 9.

The situation of the last example, where E(Fq ) Zn • Zn , makes it more

di¬cult to ¬nd the order of the group of points, but is fairly rare, as the next

result shows.

PROPOSITION 4.16

Let E be an elliptic curve over Fq and suppose

Zn • Zn

E(Fq )

for some integer n. Then either q = n2 + 1 or q = n2 ± n + 1 or q = (n ± 1)2 .

© 2008 by Taylor & Francis Group, LLC

108 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

√

PROOF By Hasse™s theorem, n2 = q + 1 ’ a, with |a| ¤ 2 q. To prove

the proposition, we use the following lemma, which puts a severe restriction

on a.

LEMMA 4.17

a ≡ 2 (mod n).

PROOF Let p be the characteristic of Fq . Then p n; otherwise, there

would be p2 points in E[p], which is impossible in characteristic p by Theo-

rem 3.2.

Since E[n] ⊆ E(Fq ), Corollary 3.11 implies that the nth roots of unity

are in Fq , so q ’ 1 must be a multiple of n (see Appendix C). Therefore,

a = q + 1 ’ n2 ≡ 2 (mod n).

Write a = 2 + kn for some integer k. Then

n2 = q + 1 ’ a = q ’ 1 ’ kn, so q = n2 + kn + 1.

By Hasse™s theorem,

√

|2 + kn| ¤ 2 q.

Squaring this last inequality yields

4 + 4kn + k 2 n2 ¤ 4q = 4(n2 + kn + 1).

Therefore, |k| ¤ 2. The possibilities k = 0, ±1, ±2 give the values of q listed

in the proposition. This completes the proof of Proposition 4.16.

Most values of q are not of the form given in the proposition, and even

Zn • Zn (only a small

for such q most elliptic curves do not have E(Fq )

2

fraction have order n ), so we can regard Zn • Zn as rare.

More generally, most q are such that all elliptic curves over Fq have points

√

of order greater than 4 q (Exercise 4.6). Therefore, with a little luck, we can

usually ¬nd points with orders that allow us to determine #E(Fq ).

The following result of Mestre shows that for E de¬ned over Fp , there is

a point of su¬ciently high order on either E or its quadratic twist. The

quadratic twist of E is de¬ned as follows. Let d ∈ F— be a quadratic non-

p

2 3

residue mod p. If E has equation y = x + Ax + B, then the quadratic twist

E has the equation y 2 = x3 + Ad2 x + Bd3 (see Exercise 2.23). By Exercise

4.10, if #E(Fp ) = p + 1 ’ a then E has p + 1 + a points. Once we know the

order of one of these two groups, we know a and therefore know the order of

both groups.

© 2008 by Taylor & Francis Group, LLC

109

SECTION 4.3 DETERMINING THE GROUP ORDER

PROPOSITION 4.18

Let p > 229 be prime and let E be an elliptic curve over Fp . Either E or

its quadratic twist E has a point P whose order has only one multiple in the

√ √

interval p + 1 ’ 2 p, p + 1 + 2 p .

PROOF Let

Zm • ZM , Zn • ZN ,

E(Fp ) E (Fp )

with m|M and n|N . If mM = #E(Fp ) = p + 1 ’ a, then nN = #E (Fp ) =

p + 1 + a. Since m|M and n|N , we have m2 |p + 1 ’ a and n2 |p + 1 + a.

Therefore, gcd(m2 , n2 )|2a.

Since E[m] ⊆ E(Fp ), then µm ⊆ F— by Corollary 3.11, so p ≡ 1 (mod m).

p

Therefore, 2 ’ a ≡ p + 1 ’ a ≡ 0 (mod m). Similarly, 2 + a ≡ 0 (mod n).

Therefore, gcd(m, n)|(2 ’ a) + (2 + a) = 4, and gcd(m2 , n2 )|16.

If 4|m and 4|n, then 16| gcd(m2 , n2 ), which divides 2a. Then 8|a, which is

impossible since then 2’a ≡ 0 (mod m) implies 2’0 ≡ 0 (mod 4). Therefore,

gcd(m2 , n2 )|4. This implies that the least common multiple of m2 and n2 is

a multiple of m2 n2 /4.

Let φ be the pth power Frobenius endomorphism for E. Since E[n] ⊆

E(Fp ), it follows that φ acts trivially on E[n]. Choose a basis for E[n2 ]. The

action of φ on E[n2 ] is given by a matrix of the form

1 + sn tn

.

un 1 + vn

By Proposition 4.11, we have a ≡ 2 + (s + v)n (mod n2 ) and p ≡ 1 + (s + v)n

(mod n2 ). Therefore, 4p’a2 ≡ 0 (mod n2 ). Similarly, 4p’a2 ≡ 0 (mod m2 ).

It follows that the least common multiple of m2 and n2 divides 4p ’ a2 , so

m2 n2

¤ 4p ’ a2 .

4

√

Suppose that both M and N are less than 4 p. Then, since a2 < 4p,

(p ’ 1)2 < (p + 1)2 ’ a2 = (p + 1 ’ a)(p + 1 + a) = mM nN

√2

1/2

< 4(4p ’ a2 ) (4 p) ¤ 64p3/2 .

A straightforward calculation shows that this implies that p < 4100. We have

therefore shown that if p > 4100, then either M or N must be greater than

√

√

4 p. This means that either E or E has a point of order greater than 4 p.

Therefore, there can be at most one multiple of this order in the interval

√ √

p + 1 ’ 2 p, p + 1 + 2 p . This proves the theorem for p > 4100.

Suppose now that 457 < p < 4100. A straightforward computation shows

√

that there are no integers a, m, n with |a| < 2 p such that

© 2008 by Taylor & Francis Group, LLC

110 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

1. m2 |p + 1 ’ a

2. n2 |p + 1 + a

√

3. (p + 1 ’ a)/m < 4 p

√

4. (p + 1 + a)/n < 4 p.

Therefore, the theorem is true for p > 457.

For p = 457, we may take a = 10, m = 8, n = 6, which correspond

to the groups Z8 • Z56 and Z6 • Z78 (and can be realized by the curves

E : y 2 = x3 ’125 and its quadratic twist E : y 2 = x3 ’1). Note, however, that

√ √

the only multiple of 56 in the interval 457 + 1 ’ 2 457, 457 + 1 + 2 457 =

(415.2, 500.8) is 448, which is the order of E(F457 ). Similarly, the only mul-

tiple of 78 in this interval is 468, which is the order of E (F457 ). Therefore,

the theorem still holds in this case.

In fact, the search for a, m, n can be extended in this way to 229 < p ¤ 457,

with conditions (3) and (4) replaced by

3™. there is more than one multiple of (p + 1 ’ a)/m in the interval

√

√

p + 1 ’ 2 p, p + 1 + 2 p

4™. there is more than one multiple of (p + 1 + a)/m in the interval

√ √

p + 1 ’ 2 p, p + 1 + 2 p .

No values of a, m, n exist satisfying these conditions, so the theorem holds.

Example 4.10

The theorem is false for p = 229. Consider the curve E : y 2 = x3 ’ 1.

Z6 • Z42 . Therefore, 42P = ∞ for

A calculation shows that E(F229 )

all P ∈ E(F229 ). The Hasse bound says that 200 ¤ #E(F229 ) ¤ 260, so the

existence of a point of order 42 allows both the values 210 and 252. Since 2 is a

quadratic nonresidue mod 229, the curve E : y 2 = x3 ’8 is the quadratic twist

Z4 • Z52 . Therefore, 52P = ∞

of E. A calculation shows that E (F229 )

for all P ∈ E (F229 ). The existence of a point of order 52 allows both the

values 208 and 260. Therefore, neither E nor its quadratic twist E has a

point whose order has only one multiple in the Hasse interval.

Suppose E(Fq ) Zn1 • Zn2 with n1 |n2 . Then the order of every element

divides n2 . If we choose some random points and compute their orders, what

is the chance that the least common multiple of these orders is n2 ? Let P1 , P2

be points of orders n1 , n2 such that every P ∈ E(Fq ) is uniquely expressible in

the form P = a1 P1 + a2 P2 with 0 ¤ ai < ni . Let p be a prime dividing n2 . If

we take a random point P , then the probability is 1 ’ 1/p that p a2 . If p a2 ,

then the order of P contains the highest power of p possible. If p is large,

then this means that it is very likely that the order of one randomly chosen

© 2008 by Taylor & Francis Group, LLC

111

SECTION 4.3 DETERMINING THE GROUP ORDER

point will contribute the correct power of p to the least common multiple of

the orders of the points. If p is small, say p = 2, then the probability is at

least 1/2. This means that if we choose several randomly chosen points, the

least common multiples of their orders should still have the correct power of

p. The conclusion is that if we choose several random points and compute the

least common multiple of their orders, it is very likely that we will obtain n2 ,

which is as large as possible.

The following result of Cremona and Harley shows that knowledge of n2

usually determines the group structure.

PROPOSITION 4.19

Zn1 • Zn2 with n1 |n2 .

Let E be an elliptic curve over Fq . Write E(Fq )

Suppose that q is not one of the following:

3, 4, 5, 7, 9, 11, 13, 17, 19, 23, 25, 27, 29, 31, 37,

43, 61, 73, 181, 331, 547.

Then n2 uniquely determines n1 .

PROOF Fix q and suppose there exist n2 , x, y (regard x, y as two possible

values of n1 ) with

1. x, y|n2

√ √

2 2

q’1 ¤ n2 x < n2 y ¤

2. q+1

(so the groups of order n2 x and n2 y satisfy the bounds in Hasse™s theorem).

Our ¬rst goal is to show that if n2 , x, y satisfying (1) and (2) exist then

q ¤ 4612.

Let d = gcd(x, y). Then n2 = dn2 , x = x/d, y = y/d also satisfy (1), (2).

So we may assume that gcd(x, y) = 1. Since n2 y ’ n2 x > 0,

√ √ √

2 2

n2 ¤ n2 y ’ n2 x ¤ ( q + 1) ’ ( q ’ 1) = 4 q.

Since x, y|n2 , we have xy|n2 , hence xy ¤ n2 . Therefore,

√

x2 ¤ xy ¤ n2 ¤ 4 q,

which implies that

√ √ √ 1/2

2

( q ’ 1) ¤ n2 x ¤ (4 q) (4 q) .

√ 2

q ’ 1 > 8q 3/4 when q ≥ 4613. Therefore, we must have q ¤ 4612.

But

The values of q ¤ 4612 can be checked on a computer to get a much smaller

list of possibilities for q. However, we can speed up the search with the

following observations.

© 2008 by Taylor & Francis Group, LLC

112 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

√ √ √

2

q ’ 1 ¤ n2 x ¤ 4 qx implies that x > q ’ 2 /4. Second,

First,

√ √

2 2

y 2 ¤ n2 y ¤ q + 1 . Third, xy 2 = (xy)y ¤ n2 y ¤ q + 1 . Finally,

n1 |q ’ 1 (by Corollary 3.11), so x, y|q ’ 1.

Therefore, we should look for values of q ¤ 4612 that are primes or prime

powers and such that q ’ 1 has divisors x, y with

1. gcd(x, y) = 1

√ √

q ’ 2 /4 < x < y ¤ q + 1

2.

√ 2

3. xy 2 ¤ q+1 .

The values of q for which such x, y exist are those on the list in the statement

of the theorem, plus the ¬ve values q = 49, 81, 121, 169, 841. Therefore, for

all other q, a number n2 cannot have two possible values x, y for n1 , so n1 is

uniquely determined.

We need to eliminate the remaining ¬ve values. For example, consider

q = 49. One solution is x = 2, y = 3, n2 = 18, which corresponds to #E(Fq ) =

√ 2

q’1 ,

36 and 54. By Theorem 4.4, or by Exercise 4.14, if #E(Fq ) =

Z√q’1 • Z√q’1 . Therefore, if #E(F49 ) = 36, we must have

then E(Fq )

n1 = n2 = 6. This arises from x = 2 after multiplying by 3 (recall that

we removed d = gcd(x, y) from x, y in order to make them relatively prime).

Multiplying y = 3 by d = 3 yields n1 = 9, n2 = 6, which does not satisfy n1 |n2 .

Therefore, the solution x = 2, y = 3 for q = 49 is eliminated. Similarly, all

solutions for all of the ¬ve values q = 49, 81, 121, 169, 841 can be eliminated.

This completes the proof.

.

4.3.4 Baby Step, Giant Step

Let P ∈ E(Fq ). We want to ¬nd the order of P . First, we want to ¬nd

an integer k such that kP = ∞. Let #E(Fq ) = N . By Lagrange™s theorem,

√

N P = ∞. Of course, we might not know N yet, but we know that q+1’2 q ¤

√

N ¤ q + 1 + 2 q. We could try all values of N in this range and see which

√

ones satisfy N P = ∞. This takes around 4 q steps. However, it is possible

to speed this up to around 4q 1/4 steps by the following algorithm.

1. Compute Q = (q + 1)P .

2. Choose an integer m with m > q 1/4 . Compute and store the points jP

for j = 0, 1, 2, . . . , m.

3. Compute the points

Q + k(2mP ) for k = ’m, ’(m ’ 1), . . . , m

© 2008 by Taylor & Francis Group, LLC

113

SECTION 4.3 DETERMINING THE GROUP ORDER

until there is a match Q + k(2mP ) = ±jP with a point (or its negative)

on the stored list.

4. Conclude that (q + 1 + 2mk “ j)P = ∞. Let M = q + 1 + 2mk “ j.

5. Factor M . Let p1 , . . . , pr be the distinct prime factors of M .

6. Compute (M/pi )P for i = 1, . . . , r. If (M/pi )P = ∞ for some i, replace

M with M/pi and go back to step (5). If (M/pi )P = ∞ for all i then

M is the order of the point P .

7. If we are looking for the #E(Fq ), then repeat steps (1)-(6) with ran-

domly chosen points in E(Fq ) until the least common multiple of the

√ √

orders divides only one integer N with q + 1 ’ 2 q ¤ N ¤ q + 1 + 2 q.

Then N = #E(Fq ).

There are two points that must be addressed.

I. Assuming that there is a match, this method clearly produces an integer

that annihilates P . But why is there a match?

LEMMA 4.20

Let a be an integer with |a| ¤ 2m2 . There exist integers a0 and a1 with

’m < a0 ¤ m and ’m ¤ a1 ¤ m such that

a = a0 + 2ma1 .

Let a0 ≡ a (mod 2m), with ’m < a0 ¤ m and a1 = (a ’ a0 )/2m.

PROOF

Then

|a1 | ¤ (2m2 + m)/2m < m + 1.

Let a = a0 + 2ma1 be as in the lemma and let k = ’a1 . Then

Q + k(2mP ) = (q + 1 ’ 2ma1 )P

= (q + 1 ’ a + a0 )P = N P + a0 P

= a0 P = ±jP,

where j = |a0 |. Therefore, there is a match.

II. Why does step (6) yield the order of P ?

LEMMA 4.21

Let G be an additive group (with identity element 0) and let g ∈ G. Suppose

M g = 0 for some positive integer M . Let p1 , . . . , pr be the distinct primes

dividing M . If (M/pi )g = 0 for all i, then M is the order of g.

© 2008 by Taylor & Francis Group, LLC

114 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

PROOF Let k be the order of g. Then k|M . Suppose k = M . Let pi be

a prime dividing M/k. Then pi k|M , so k|(M/pi ). Therefore, (M/pi )g = 0,

contrary to assumption. Therefore k = M .

Therefore, step (6) ¬nds the order of P .

REMARK 4.22 (1) To save storage space, it might be more e¬cient to

store only the x coordinates of the points jP (along with the corresponding

integer j), since looking for a match with ±jP only requires the x-coordinate

(assuming we are working with a Weierstrass equation). When a match is

found, the two possible y-coordinates can be recomputed.

(2) Computing Q + k(2mP ) can be done by computing Q and 2mP once

for all. To get from Q + k(2mP ) to Q + (k + 1)(2mP ), simply add 2mP rather

than recomputing everything. Similarly, once jP has been computed, add P

to get (j + 1)P .

(3) We are assuming that we can factor M . If not, we can at least ¬nd all

the small prime factors pi and check that (M/pi )P = ∞ for these. Then M

will be a good candidate for the order of P .

(4) Why is the method called “Baby Step, Giant Step”? The baby steps

are from a point jP to (j + 1)P . The giant steps are from a point k(2mP )

to (k + 1)(2mP ), since we take the “bigger” step 2mP .

Example 4.11

Let E be the elliptic curve y 2 = x3 ’ 10x + 21 over F557 , as in Example 4.7.

Let P = (2, 3). We follow the procedure above.

1. Q = 558P = (418, 33).

2. Let m = 5, which is greater than 5571/4 . The list of jP is

∞, (2, 3), (58, 164), (44, 294), (56, 339), (132, 364).

3. When k = 1, we have Q + k(2mP ) = (2, 3), which matches the point on

our list for j = 1.

4. We have (q + 1 + 2mk ’ j)P = 567P = ∞.

5. Factor 567 = 34 · 7. Compute (567/3)P = 189P = ∞. We now have 189

as a candidate for the order of P .

6. Factor 189 = 33 7. Compute (189/3)P = (38, 535) = ∞ and (189/7)P =

(136, 360) = ∞. Therefore 189 is the order of P .

As pointed out in Example 4.7, this su¬ces to determine that #E(F557 ) =

567.

© 2008 by Taylor & Francis Group, LLC

115

SECTION 4.4 A FAMILY OF CURVES

4.4 A Family of Curves

In this section we give an explicit formula for the number of points in E(Fp ),

where E is the elliptic curve

y 2 = x3 ’ kx,

and k ≡ 0 (mod p). Counting the points on this curve mod a prime p has a

long history, going back at least to Gauss.

THEOREM 4.23

Let p be an odd prime and let k ≡ 0 (mod p). Let Np = #E(Fp ), where E

is the elliptic curve

y 2 = x3 ’ kx.

1. If p ≡ 3 (mod 4), then Np = p + 1.

2. If p ≡ 1 (mod 4), write p = a2 + b2 , where a, b are integers with b even

and a + b ≡ 1 (mod 4). Then

§

⎨ p + 1 ’ 2a if k is a fourth power mod p

Np = p + 1 + 2a if k is a square mod p but not a 4th power mod p

©

p + 1 ± 2b if k is not a square mod p.

The proof of the theorem will take the rest of this section.

The integer a is uniquely determined by the conditions in the theorem, and

b is uniquely determined up to sign. When k is not a square mod p, the proof

below does not determine the sign of b. This is a much more delicate problem

and we omit it.

Example 4.12

Let p = 61 = (’5)2 + 62 , where we chose the negative sign on 5 so that

’5 + 6 ≡ 1 (mod 4). Since k = 1 is a fourth power, the number of points on

y 2 = x3 ’ x is p + 1 ’ 2(’5) = 72.

It is well known that every prime p ≡ 1 (mod 4) is a sum of two squares

(this follows from Proposition 4.27 below). The next lemma shows that a and

b are uniquely determined up to order and sign.

LEMMA 4.24

Suppose p is prime and a, b, c, d are integers such that a2 + b2 = p = c2 + d2 .

Then a = ±c and b = ±d, or a = ±d and b = ±c.

© 2008 by Taylor & Francis Group, LLC

116 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

PROOF We have (a/b)2 +1 ≡ 0 ≡ (c/d)2 +1 (mod p), so a/b ≡ ±(c/d). By

changing the sign of c if necessary, we may assume that a/b ≡ c/d (mod p),

hence ad ’ bc ≡ 0 (mod p). A quick calculation shows that

p2 = (ac + bd)2 + (bc ’ ad)2 . (4.2)

Suppose ad = bc. Then (4.2) implies that ac + bd = ±p, so

±ap = a2 c + abd = a2 c + b2 c = pc.

Hence, ±a = c. It follows that b = ±d.

Now suppose ad = bc. Since ad ’ bc ≡ 0 (mod p), we have (ad ’ bc)2 ≥ p2 .

Since (ac + bd)2 ≥ 0, it follows from (4.2) that ad ’ bc = ±p and ac + bd = 0.

Therefore,

±cp = acd ’ bc2 = ’bd2 ’ bc2 = ’bp,

so c = ±b. This implies that d = ±a.

If we require that a is odd and b is even, then a and b are uniquely deter-

mined up to sign. Suppose b ≡ 2 (mod 4). Then a + b ≡ 1 (mod 4) for a

unique choice of the sign of a. Similarly, if b ≡ 0 (mod 4), there is a unique

choice of the sign of a that makes a + b ≡ 1 (mod 4). Therefore, the integer

a in the lemma is uniquely determined by p if we require that a is odd and

a + b ≡ 1 (mod 4).

The main part of the proof of Theorem 4.23 involves the case p ≡ 1 (mod 4),

so let™s treat the case p ≡ 3 (mod 4) ¬rst. The main point is that ’1 is

not a square mod p (Proof: if x2 ≡ ’1, then 1 ≡ xp’1 ≡ (x2 )(p’1)/2 ≡

(’1)(p’1)/2 ≡ (’1)odd = ’1, contradiction). Moreover, a nonsquare times

a nonsquare is a square mod p. Therefore x3 ’ kx is a nonzero square mod

p if and only if (’x)3 ’ k(’x) = ’(x3 ’ kx) is not a square mod p. Let™s

count points on E. Whenever x3 ’ kx = 0, we obtain one point (x, 0). For

the remaining values of x, we pair up x and ’x. One of these gives two

points (the one that makes x3 ’ kx a square) and the other gives no points.

Therefore, each pair x, ’x gives two points. Therefore, we obtain a total of p

points. The point ∞ gives one more, so we have p + 1 points.

Now assume p ≡ 1 (mod 4). The proof, which takes the rest of this sec-

tion, involves several steps and counts the points in terms of Jacobi sums.

Rather than count the points on E directly, we make the transformation (see

Theorem 2.17)

4(v + 1)

2(v + 1)

, y= ,

x= 2 u3

u

which changes E into the curve C given by

v 2 = (k/4)u4 + 1.

The inverse transformation is

2x3

2x

v = ’1 + 2 .

,

u=

y y

© 2008 by Taylor & Francis Group, LLC

117

SECTION 4.4 A FAMILY OF CURVES

We™ll count the points on C mod p.

First, there are a few special points for the transformation from E to C. The

point ∞ on E corresponds to (0, 1) on C. The point (0, 0) on E corresponds

to (0, ’1) on C (see Theorem 2.17). If k is a square mod p, then the two

√

2-torsion points (± k, 0) correspond to the point at in¬nity on C. Therefore,

#E(Fp ) = #{(u, v) ∈ Fp — Fp | v 2 = (k/4)u4 + 1} + δ,

where

2 if k is a square mod p

δ=

0 if not.

Let g be a primitive root mod p, which means that

F— = {g j | 0 ¤ j < p ’ 1}.

p

√

’1 ∈ C. De¬ne

Let i =

χ2 (g j ) = (’1)j χ4 (g j ) = ij .

and

Then χ2 and χ4 can be regarded as homomorphisms from F— to {±1, ±i}.

p

Note that χ2 = χ2 . The following lemma gets us started.

4

LEMMA 4.25

Let p ≡ 1 (mod 4) be prime and let x ∈ F— . Then

p

1

F— 2

#{u ∈ | u = x} = χ2 (x) ,

p

=0

and

3

F— 4

#{u ∈ | u = x} = χ4 (x) .

p

=0

PROOF Since p ≡ 1 (mod 4), there are 4 fourth roots of 1 in F— . There-

p

fore, if there is a solution to u4 ≡ x, there are 4 solutions. Write x ≡ g j

(mod p). Then x is a fourth power mod p if and only if j ≡ 0 (mod 4). We

have

3 3

4 if j ≡ 0 (mod 4)

ij =

χ4 (x) =

0 if j ≡ 0 (mod 4),

=0 =0

which is exactly the number of u with u4 ≡ x. This proves the second half of

the lemma. The proof of the ¬rst half is similar.

If, instead, we sum over the elements of F— , we have the following result.

p

© 2008 by Taylor & Francis Group, LLC

118 CHAPTER 4 ELLIPTIC CURVES OVER FINITE FIELDS

LEMMA 4.26

Let p ≡ 1 (mod 4) be prime. Then

p’1 ≡ 0 (mod 4)

if

χ4 (b) =

≡ 0 (mod 4).

0 if

b∈F—

p

PROOF If ≡ 0 (mod 4), all the terms in the sum are 1, so the sum is

p ’ 1. If ≡ 0 (mod 4), then χ4 (g) = 1. Multiplying by g permutes the

elements of F— , so

p

χ4 (g) χ4 (b) = χ4 (gb) = χ4 (c) ,

b∈F— b∈F— c∈F—

p p p

which is the original sum. Since χ4 (g) = 1, the sum must be 0.

De¬ne the Jacobi sums by

J(χj , χ4 ) = χ2 (a)j χ4 (1 ’ a) .

2

—

a∈Fp

a=1

PROPOSITION 4.27

J(χ2 , χ2 ) = ’1 and |J(χ2 , χ4 )|2 = p.

4

PROOF The ¬rst equality is proved as follows.

J(χ2 , χ2 ) = χ2 (a)χ4 (1 ’ a)2 = χ2 (a)χ2 (1 ’ a),

4

— a=0,1

a∈Fp

a=1

since χ2 = χ2 . Since χ2 (a) = ±1, we have χ2 (a) = χ2 (a)’1 so the sum equals