. 1
( 3)



>>

Chapter 4
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

. 1
( 3)



>>