стр. 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  and ,
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)СОДЕРЖАНИЕ >>