Chapter 3
Torsion Points

The torsion points, namely those whose orders are п¬Ѓnite, play an important
role in the study of elliptic curves. WeвЂ™ll see this in Chapter 4 for elliptic
curves over п¬Ѓnite п¬Ѓelds, where all points are torsion points, and in Chapter
8, where we use 2-torsion points in a procedure known as descent. In the
present chapter, we п¬Ѓrst consider the elementary cases of 2- and 3-torsion,
then determine the general situation. Finally, we discuss the important Weil
and Tate-Lichtenbaum pairings.

3.1 Torsion Points
Let E be an elliptic curve deп¬Ѓned over a п¬Ѓeld K. Let n be a positive integer.
We are interested in

E[n] = {P в€€ E(K) | nP = в€ћ}

(recall that K = algebraic closure of K). We emphasize that E[n] contains
points with coordinates in K, not just in K.
When the characteristic of K is not 2, E can be put in the form y 2 = cubic,
and it is easy to determine E. Let

y 2 = (x в€’ e1 )(x в€’ e2 )(x в€’ e3 ),

with e1 , e2 , e3 в€€ K. A point P satisп¬Ѓes 2P = в€ћ if and only if the tangent line
at P is vertical. It is easy to see that this means that y = 0, so

E = {в€ћ, (e1 , 0), (e2 , 0), (e3 , 0)}.

As an abstract group, this is isomorphic to Z2 вЉ• Z2 .
The situation in characteristic 2 is more subtle. In Section 2.8 we showed
that E can be assumed to have one of the following two forms:

y 2 + xy + x3 + a2 x2 + a6 = 0 (II) y 2 + a3 y + x3 + a4 x + a6 = 0.
(I) or

77

В© 2008 by Taylor & Francis Group, LLC
78 CHAPTER 3 TORSION POINTS

In the п¬Ѓrst case, a6 = 0 and in the second case, a3 = 0 (otherwise the curves
would be singular). If P = (x, y) is a point of order 2, then the tangent at
P must be vertical, which means that the partial derivative with respect to
y must vanish. In case I, this means that x = 0. Substitute x = 0 into (I)
в€љ в€љ
to obtain 0 = y 2 + a6 = (y + a6 )2 . Therefore (0, a6 ) is the only point of
order 2 (square roots are unique in characteristic 2), so
в€љ
E = {в€ћ, (0, a6 )}.

As an abstract group, this is isomorphic to Z2 .
In case II, the partial derivative with respect to y is a3 = 0. Therefore,
there is no point of order 2, so

E = {в€ћ}.

We summarize the preceding discussion as follows.

PROPOSITION 3.1
Let E be an elliptic curve over a п¬Ѓeld K. If the characteristic of K is not 2,
then
E Z2 вЉ• Z2 .
If the characteristic of K is 2, then

E 0 or Z2 .

Now letвЂ™s look at E. Assume п¬Ѓrst that the characteristic of K is not 2
or 3, so that E can be given by the equation y 2 = x3 + Ax + B. A point P
satisп¬Ѓes 3P = в€ћ if and only if 2P = в€’P . This means that the x-coordinate
of 2P equals the x-coordinate of P (the y-coordinates therefore diп¬Ђer in sign;
of course, if they were equal, then 2P = P , hence P = в€ћ). In equations, this
becomes
3x2 + A
m в€’ 2x = x, where m =
2
.
2y
Using the fact that y 2 = x3 + Ax + B, we п¬Ѓnd that

(3x2 + A)2 = 12x(x3 + Ax + B).

This simpliп¬Ѓes to
3x4 + 6Ax2 + 12Bx в€’ A2 = 0.
The discriminant of this polynomial is в€’6912(4A3 +27B 2 )2 , which is nonzero.
Therefore the polynomial has no multiple roots. There are 4 distinct values
of x (in K), and each x yields two values of y, so we have eight points of order
3. Since в€ћ is also in E, we see that E is a group of order 9 in which
every element is 3-torsion. It follows that

Z3 вЉ• Z3 .
E

В© 2008 by Taylor & Francis Group, LLC
79
SECTION 3.1 TORSION POINTS

The case where K has characteristic 2 is Exercise 3.2.
Now letвЂ™s look at characteristic 3. We may assume that E has the form
y = x3 + a2 x2 + a4 x + a6 . Again, we want the x-coordinate of 2P to equal
2

the x-coordinate of P . We calculate the x-coordinate of 2P by the usual
procedure and set it equal to the x-coordinate x of P . Some terms disappear
because 3 = 0. We obtain
2
2a2 x + a4
в€’ a2 = 3x = 0.
2y

This simpliп¬Ѓes to (recall that 4 = 1)

a2 x3 + a2 a6 в€’ a2 = 0.
4

1/3
Note that we cannot have a2 = a4 = 0 since then x3 + a6 = (x + a6 )3 has
multiple roots, so at least one of a2 , a4 is nonzero.
If a2 = 0, then we have в€’a2 = 0, which cannot happen, so there are no
4
values of x. Therefore E = {в€ћ} in this case.
If a2 = 0, then we obtain an equation of the form a2 (x3 + a) = 0, which has
a single triple root in characteristic 3. Therefore, there is one value of x, and
two corresponding values of y. This yields 2 points of order 3. Since there
is also the point в€ћ, we see that E has order 3, so E Z3 as abstract
groups.
The general situation is given by the following.

THEOREM 3.2
Let E be an elliptic curve over a п¬Ѓeld K and let n be a positive integer. If
the characteristic of K does not divide n, or is 0, then

Zn вЉ• Zn .
E[n]

If the characteristic of K is p > 0 and p|n, write n = pr n with p n . Then

Zn вЉ• Zn Zn вЉ• Zn .
E[n] or

The theorem will be proved in Section 3.2.
An elliptic curve E in characteristic p is called ordinary if E[p] Zp . It
is called supersingular if E[p] 0. Note that the terms вЂњsupersingularвЂќ
and вЂњsingularвЂќ (as applied to bad points on elliptic curves) are unrelated.
In the theory of complex multiplication (see Chapter 10), the вЂњsingularвЂќ j-
invariants are those corresponding to elliptic curves with endomorphism rings
larger than Z, and the вЂњsupersingularвЂќ j-invariants are those corresponding to
elliptic curves with the largest possible endomorphism rings, namely, orders
in quaternion algebras.
Let n be a positive integer not divisible by the characteristic of K. Choose
a basis {ОІ1 , ОІ2 } for E[n] Zn вЉ•Zn . This means that every element of E[n] is

В© 2008 by Taylor & Francis Group, LLC
80 CHAPTER 3 TORSION POINTS

expressible in the form m1 ОІ1 + m2 ОІ with integers m1 , m2 . Note that m1 , m2
are uniquely determined mod n. Let О± : E(K) в†’ E(K) be a homomorphism.
Then О± maps E[n] into E[n]. Therefore, there are a, b, c, d в€€ Zn such that
О±(ОІ1 ) = aОІ1 + cОІ2 , О±(ОІ2 ) = bОІ1 + dОІ2 .
Therefore each homomorphism О± : E(K) в†’ E(K) is represented by a 2 Г— 2
matrix
ab
О±n = .
cd
Composition of homomorphisms corresponds to multiplication of the corre-
sponding matrices.
In many cases, the homomorphism О± will be taken to be an endomorphism,
which means that it is given by rational functions (see Section 2.9). But О±
can also come from an automorphism of K that п¬Ѓxes K. This leads to the im-
portant subject of representations of Galois groups (that is, homomorphisms
from Galois groups to groups of matrices).

Example 3.1
Let E be the elliptic curve deп¬Ѓned over R by y 2 = x3 в€’ 2, and let n = 2.
Then
E = {в€ћ, (21/3 , 0), (О¶21/3 , 0), (О¶ 2 21/3 , 0)},
where О¶ is a nontrivial cube root of unity. Let
ОІ1 = (21/3 , 0), ОІ2 = (О¶21/3 , 0).
Then {ОІ1 , ОІ2 } is a basis for E, and ОІ3 = (О¶ 2 21/3 , 0) = ОІ1 + ОІ2 .
Let О± : E(C) в†’ E(C) be complex conjugation: О±(x, y) = (x, y), where
the bar denotes complex conjugation. It is easy to verify that О± is a homo-
morphism. In fact, since all the coeп¬ѓcients of the formulas for the group
law have real coeп¬ѓcients, we have P1 + P2 = P1 + P2 . This is the same as
О±(P1 ) + О±(P2 ) = О±(P1 + P2 ). We have
О±(ОІ1 ) = 1 В· ОІ1 + 0 В· ОІ2 , О±(ОІ2 ) = ОІ3 = 1 В· ОІ1 + 1 В· ОІ2 .
11
. Note that О± в—¦ О± is the identity,
Therefore we obtain the matrix О±2 =
01
2
which corresponds to the fact that О±2 is the identity matrix mod 2.

3.2 Division Polynomials
The goal of this section is to prove Theorem 3.2. WeвЂ™ll also obtain a few
other results that will be needed in proofs in Section 4.2.

В© 2008 by Taylor & Francis Group, LLC
81
SECTION 3.2 DIVISION POLYNOMIALS

In order to study the torsion subgroups, we need to describe the map on
an elliptic curve given by multiplication by an integer. As in Section 2.9, this
is an endomorphism of the elliptic curve and can be described by rational
functions. We shall give formulas for these functions.
We start with variables A, B. Deп¬Ѓne the division polynomials П€m в€€
Z[x, y, A, B] by
П€0 = 0
П€1 = 1
П€2 = 2y
П€3 = 3x4 + 6Ax2 + 12Bx в€’ A2
П€4 = 4y(x6 + 5Ax4 + 20Bx3 в€’ 5A2 x2 в€’ 4ABx в€’ 8B 2 в€’ A3 )
П€2m+1 = П€m+2 П€m в€’ П€mв€’1 П€m+1 for m в‰Ґ 2
3 3

П€2m = (2y)в€’1 (П€m )(П€m+2 П€mв€’1 в€’ П€mв€’2 П€m+1 ) for m в‰Ґ 3.
2 2

LEMMA 3.3
П€n is a polynomial in Z[x, y 2 , A, B] when n is odd, and П€n is a polynomial
in 2yZ[x, y 2 , A, B] when n is even.

PROOF The lemma is true for n в‰¤ 4. Assume, by induction, that it holds
for all n < 2m. We may assume that 2m > 4, so m > 2. Then 2m > m + 2,
so all polynomials appearing in the deп¬Ѓnition of П€2m satisfy the induction
assumptions. If m is even, then П€m , П€m+2 , П€mв€’2 are in 2yZ[x, y 2 , A, B], from
which it follows that П€2m is in 2yZ[x, y 2 , A, B]. If m is odd, then П€mв€’1 and
П€m+1 are in 2yZ[x, y 2 , A, B], so again we п¬Ѓnd that П€2m is in 2yZ[x, y 2 , A, B].
Therefore, the lemma holds for n = 2m. Similarly, it holds for n = 2m + 1.

Deп¬Ѓne polynomials
П†m = xП€m в€’ П€m+1 П€mв€’1
2

П‰m = (4y)в€’1 (П€m+2 П€mв€’1 в€’ П€mв€’2 П€m+1 ).
2 2

LEMMA 3.4
П†n в€€ Z[x, y 2 , A, B] for all n. If n is odd, then П‰n в€€ yZ[x, y 2 , A, B]. If n is
even, then П‰n в€€ Z[x, y 2 , A, B].

PROOF If n is odd, then П€n+1 and П€nв€’1 are in yZ[x, y 2 , A, B], so their
product is in Z[x, y 2 , A, B]. Therefore, П†n в€€ Z[x, y 2 , A, B]. If n is even, the
proof is similar.
The facts that y в€’1 П‰n в€€ Z[x, y 2 , A, B] for odd n and П‰n в€€ 1 Z[x, y 2 , A, B]
2
for even n follow from Lemma 3.3, and these are all that we need for future

В© 2008 by Taylor & Francis Group, LLC
82 CHAPTER 3 TORSION POINTS

applications. However, to get rid of the extra 2 in the denominator, we proceed
as follows. Induction (treating separately the various possibilities for n mod
4) shows that
2
в€’1)/4
П€n в‰Ў (x2 + A)(n (mod 2) when n is odd

and
n 2
(2y)в€’1 П€n в‰Ў (x2 + A)(n в€’4)/4 (mod 2) when n is even.
2

A straightforward calculation now yields the lemma.

We now consider an elliptic curve

y 2 = x3 + Ax + B, 4A3 + 27B 2 = 0.
E:

We donвЂ™t specify what ring or п¬Ѓeld the coeп¬ѓcients A, B are in, so we continue
to treat them as variables. We regard the polynomials in Z[x, y 2 , A, B] as
polynomials in Z[x, A, B] by replacing y 2 with x3 + Ax + B. Therefore, we
2
write П†n (x) and П€n (x). Note that П€n is not necessarily a polynomial in x
2
alone, while П€n is always a polynomial in x.

LEMMA 3.5

2
П†n (x) = xn + lower degree terms
2
в€’1
П€n (x) = n2 xn
2
+ lower degree terms

PROOF In fact, we claim that
2
y(nx(n в€’4)/2 + В· В· В· ) if n is even
П€n = 2
nx(n в€’1)/2 + В· В· В· if n is odd.

This is proved by induction. For example, if n = 2m + 1 with m even, then
3
the leading term of П€m+2 П€m is
(m+2)2 в€’4 2
+ 3m 2в€’12
(m + 2)m3 y 4 x .
2

Changing y 4 to (x3 + Ax + B)2 yields
(2m+1)2 в€’1
(m + 2)m3 x .
2

3
Similarly, the leading term of П€mв€’1 П€m+1 is
(2m+1)2 в€’1
(m в€’ 1)(m + 1)3 x .
2

В© 2008 by Taylor & Francis Group, LLC
83
SECTION 3.2 DIVISION POLYNOMIALS

Subtracting and using the recursion relation shows that the leading term of
П€2m+1 is as claimed in the lemma. The other cases are treated similarly.

We can now state the main theorem.

THEOREM 3.6
Let P = (x, y) be a point on the elliptic curve y 2 = x3 + Ax + B (over some
п¬Ѓeld of characteristic not 2), and let n be a positive integer. Then

П†n (x) П‰n (x, y)
nP = , .
П€n (x) П€n (x, y)3
2

The proof will be given in Section 9.5.

COROLLARY 3.7
Let E be an elliptic curve. The endomorphism of E given by multiplication
by n has degree n2 .

PROOF From Lemma 3.5, we have that the maximum of the degrees of
the numerator and denominator of П†n (x)/П€n (x) is n2 . Therefore, the degree
2

of the endomorphism is n2 if this rational function is reduced, that is, if П†n (x)
2
and П€n (x) have no common roots. WeвЂ™ll show that this is the case. Suppose
not. Let n be the smallest index for which they have a common root.
Suppose n = 2m is even. A quick calculation shows that

П†2 (x) = x4 в€’ 2Ax2 в€’ 8Bx + A2 .

Computing the x-coordinate of 2m(x, y) in two steps by multiplying by m
and then by 2, and using the fact that

П€2 = 4y 2 = 4(x3 + Ax + B),
2

we obtain
2
П†2m П†2 (П†m /П€m )
=2
2 2
П€2m П€2 (П†m /П€m )

П†4 в€’ 2AП†2 П€m в€’ 8BП†m П€m + A2 П€m
4 6 8
m m
=
(4П€m )(П†3 + AП†m П€m + BП€m )
2 4 6
m

U
= ,
V
where U and V are the numerator and denominator of the preceding expres-
sion. To show U and V have no common roots, we need the following.

В© 2008 by Taylor & Francis Group, LLC
84 CHAPTER 3 TORSION POINTS

LEMMA 3.8
Let в€† = 4A3 + 27B 2 and let

F (x, z) = x4 в€’ 2Ax2 z 2 в€’ 8Bxz 3 + A2 z 4
G(x, z) = 4z(x3 + Axz 2 + Bz 3 )
f1 (x, z) = 12x2 z + 16Az 3
g1 (x, z) = 3x3 в€’ 5Axz 2 в€’ 27Bz 3
f2 (x, z) = 4в€†x3 в€’ 4A2 Bx2 z + 4A(3A3 + 22B 2 )xz 2 + 12B(A3 + 8B 2 )z 3
g2 (x, z) = A2 Bx3 + A(5A3 + 32B 2 )x2 z + 2B(13A3 + 96B 2 )xz 2
в€’ 3A2 (A3 + 8B 2 )z 3 .

Then
F f1 в€’ Gg1 = 4в€†z 7 and F f2 + Gg2 = 4в€†x7 .

PROOF This is veriп¬Ѓed by a straightforward calculation. Where do these
identities come from? The polynomials F (x, 1) and G(x, 1) have no common
roots, so the extended Euclidean algorithm, applied to polynomials, п¬Ѓnds
polynomials f1 (x), g1 (x) such that F (x, 1)f1 (x) + G(x, 1)g1 (x) = 1. Changing
x to x/z, multiplying by z 7 (to make everything homogeneous), then multi-
plying by 4в€† to clear denominators yields the п¬Ѓrst identity. The second is
obtained by reversing the roles of x and z.

The lemma implies that

U В· f1 (П†m , П€m ) в€’ V В· g1 (П†m , П€m ) = 4П€m в€†
2 2 14

U В· f2 (П†m , П€m ) + V В· g2 (П†m , П€m ) = 4П†7 в€†.
2 2
m

2
If U, V have a common root, then so do П†m and П€m . Since n = 2m is the п¬Ѓrst
index for which there is a common root, this is impossible.
2 2
It remains to show that U = П†2m and V = П€2m . Since U/V = П†2m /П€2m
and since U, V have no common root, it follows that П†2m is a multiple of U
2
and П€2m is a multiple of V . A quick calculation using Lemma 3.5 shows that
2
U = x4m + lower degree terms.

Lemma 3.5 and the fact that П†2m is a multiple of U imply that П†2m = U .
2 2
Therefore, V = П€2m . It follows that П†2m and П€2m have no common roots.
Now suppose that the smallest index n such that there is a common root is
2
odd: n = 2m + 1. Let r be a common root of П†n and П€n . Since

П†n = xП€n в€’ П€nв€’1 П€n+1 ,
2

and since П€n+1 П€nв€’1 is a polynomial in x, we have (П€n+1 П€nв€’1 )(r) = 0.
2
But П€nВ±1 are polynomials in x and their product vanishes at r. Therefore
П€n+Оґ (r) = 0, where Оґ is either 1 or в€’1.
2

В© 2008 by Taylor & Francis Group, LLC
85
SECTION 3.2 DIVISION POLYNOMIALS

Since n is odd, both П€n and П€n+2Оґ are polynomials in x. Moreover,

(П€n П€n+2Оґ )2 = П€n П€n+2Оґ
22

vanishes at r. Therefore П€n П€n+2Оґ vanishes at r. Since

П†n+Оґ = xП€n+Оґ в€’ П€n П€n+2Оґ ,
2

2
we п¬Ѓnd that П†n+Оґ (r) = 0. Therefore, П†n+Оґ and П€n+Оґ have a common root.
Note that n + Оґ is even.
2
When considering the case that n is even, we showed that if П†2m and П€2m
2
have a common root, then П†m and П€m have a common root. In the present
case, we apply this to 2m = n + Оґ. Since n is assumed to be the smallest
index for which there is a common root, we have
n+Оґ
в‰Ґ n.
2
2
This implies that n = 1. But clearly П†1 = x and П€1 = 1 have no common
roots, so we have a contradiction.
2
This proves that П†n and П€n have no common roots in all cases. Therefore,
as pointed out at the beginning of the proof, the multiplication by n map has
degree n2 . This completes the proof of Corollary 3.7.

Recall from Section 2.9 that if О±(x, y) = (R(x), yS(x)) is an endomorphism
of an elliptic curve E, then О± is separable if R (x) is not identically 0. Assume
n is not a multiple of the characteristic p of the п¬Ѓeld. From Theorem 3.6 we
see that the multiplication by n map has
2
xn + В· В· В·
R(x) = 2 n2 в€’1 .
+ В·В·В·
nx
2
The numerator of the derivative is n2 x2n в€’2 +В· В· В· = 0, so R (x) = 0. Therefore,
multiplication by n is separable. From Corollary 3.7 and Proposition 2.21,
E[n], the kernel of multiplication by n, has order n2 . The structure theorem
for п¬Ѓnite abelian groups (see Appendix B) says that E[n] is isomorphic to

Zn1 вЉ• Zn2 вЉ• В· В· В· вЉ• Znk ,

for some integers n1 , n2 , . . . , nk with ni |ni+1 for all i. Let be a prime dividing
n1 . Then |ni for all i. This means that E[ ] вЉ† E[n] has order k . Since we
have just proved that E[ ] has order 2 , we must have k = 2. Multiplication by
n annihilates E[n] Zn1 вЉ• Zn2 , so we must have n2 |n. Since n2 = #E[n] =
n1 n2 , it follows that n1 = n2 = n. Therefore,

Zn вЉ• Zn
E[n]

when the characteristic p of the п¬Ѓeld does not divide n.

В© 2008 by Taylor & Francis Group, LLC
86 CHAPTER 3 TORSION POINTS

It remains to consider the case where p|n. We п¬Ѓrst determine the p-power
torsion on E. By Proposition 2.28, multiplication by p is not separable. By
Proposition 2.21, the kernel E[p] of multiplication by p has order strictly less
than the degree of this endomorphism, which is p2 by Corollary 3.7. Since
every element of E[p] has order 1 or p, the order of E[p] is a power of p, hence
must be 1 or p. If E[p] is trivial, then E[pk ] must be trivial for all k. Now
suppose E[p] has order p. We claim that E[pk ] Zpk for all k. It is easy to
see that E[pk ] is cyclic. The hard part is to show that the order is pk , rather
than something smaller (for example, why canвЂ™t we have E[pk ] = E[p] Zp
for all k?). Suppose there exists an element P of order pj . By Theorem 2.22,
multiplication by p is surjective, so there exists a point Q with pQ = P . Since

pj Q = pjв€’1 P = в€ћ pj+1 Q = pj P = в€ћ,
but

Q has order pj+1 . By induction, there are points of order pk for all k. There-
fore, E[pk ] is cyclic of order pk .
We can now put everything together. Write n = pr n with r в‰Ґ 0 and p n .
Then
E[n] E[n ] вЉ• E[pr ].
We have E[n ] Zn вЉ• Zn , since p n . We have just showed that E[pr ]
0 or Zpr . Recall that
Zn вЉ• Zpr Zn pr Zn
(see Appendix A). Therefore, we obtain

Zn вЉ• Zn Zn вЉ• Zn .
E[n] or

This completes the proof of Theorem 3.2.

3.3 The Weil Pairing
The Weil pairing on the n-torsion on an elliptic curve is a major tool in the
study of elliptic curves. For example, it will be used in Chapter 4 to prove
HasseвЂ™s theorem on the number of points on an elliptic curve over a п¬Ѓnite
п¬Ѓeld. It will be used in Chapter 5 to attack the discrete logarithm problem
for elliptic curves. In Chapter 6, it will be used in a cryptographic setting.
Let E be an elliptic curve over a п¬Ѓeld K and let n be an integer not divisible
by the characteristic of K. Then E[n] Zn вЉ• Zn . Let

Вµn = {x в€€ K | xn = 1}

be the group of nth roots of unity in K. Since the characteristic of K does
not divide n, the equation xn = 1 has no multiple roots, hence has n roots in

В© 2008 by Taylor & Francis Group, LLC
87
SECTION 3.3 THE WEIL PAIRING

K. Therefore, Вµn is a cyclic group of order n. Any generator О¶ of Вµn is called
a primitive nth root of unity. This is equivalent to saying that О¶ k = 1 if
and only if n divides k.

THEOREM 3.9
Let E be an elliptic curve deп¬Ѓned over a п¬Ѓeld K and let n be a positive integer.
Assume that the characteristic of K does not divide n. Then there is a pairing

en : E[n] Г— E[n] в†’ Вµn ,

called the Weil pairing, that satisп¬Ѓes the following properties:
1. en is bilinear in each variable. This means that

en (S1 + S2 , T ) = en (S1 , T )en (S2 , T )

and
en (S, T1 + T2 ) = en (S, T1 )en (S, T2 )
for all S, S1 , S2 , T, T1 , T2 в€€ E[n].
2. en is nondegenerate in each variable. This means that if en (S, T ) = 1
for all T в€€ E[n] then S = в€ћ and also that if en (S, T ) = 1 for all
S в€€ E[n] then T = в€ћ.
3. en (T, T ) = 1 for all T в€€ E[n].
4. en (T, S) = en (S, T )в€’1 for all S, T в€€ E[n].
5. en (ПѓS, ПѓT ) = Пѓ(en (S, T )) for all automorphisms Пѓ of K such that Пѓ is
the identity map on the coeп¬ѓcients of E (if E is in Weierstrass form,
this means that Пѓ(A) = A and Пѓ(B) = B).
6. en (О±(S), О±(T )) = en (S, T )deg(О±) for all separable endomorphisms О± of
E. If the coeп¬ѓcients of E lie in a п¬Ѓnite п¬Ѓeld Fq , then the statement
also holds when О± is the Frobenius endomorphism П†q . (Actually, the
statement holds for all endomorphisms О±, separable or not. See .)

The proof of the theorem will be given in Chapter 11. In the present section,
weвЂ™ll derive some consequences.

COROLLARY 3.10
Let {T1 , T2 } be a basis of E[n]. Then en (T1 , T2 ) is a primitive nth root of
unity.

PROOF Suppose en (T1 , T2 ) = О¶ with О¶ d = 1. Then en (T1 , dT2 ) = 1.
Also, en (T2 , dT2 ) = en (T2 , T2 )d = 1 (by (1) and (3)). Let S в€€ E[n]. Then

В© 2008 by Taylor & Francis Group, LLC
88 CHAPTER 3 TORSION POINTS

S = aT1 + bT2 for some integers a, b. Therefore,
en (S, dT2 ) = en (T1 , dT2 )a en (T2 , dT2 )b = 1.
Since this holds for all S, (2) implies that dT2 = в€ћ. Since dT2 = в€ћ if and
only if n|d, it follows that О¶ is a primitive nth root of unity.

COROLLARY 3.11
If E[n] вЉ† E(K), then Вµn вЉ‚ K.

REMARK 3.12 Recall that points in E[n] are allowed to have coordinates
in K. The hypothesis of the corollary is that these points all have coordinates
in K.

PROOF Let Пѓ be any automorphism of K such that Пѓ is the identity on
K. Let T1 , T2 be a basis of E[n]. Since T1 , T2 are assumed to have coordinates
in K, we have ПѓT1 = T1 and ПѓT2 = T2 . By (5),
О¶ = en (T1 , T2 ) = en (ПѓT1 , ПѓT2 ) = Пѓ(en (T1 , T2 )) = Пѓ(О¶).
The fundamental theorem of Galois theory says that if an element x в€€ K is
п¬Ѓxed by all such automorphisms Пѓ, then x в€€ K. Therefore, О¶ в€€ K. Since О¶
is a primitive nth root of unity by Corollary 3.10, it follows that Вµn вЉ‚ K.
(Technical point: The fundamental theorem of Galois theory only implies
that О¶ lies in a purely inseparable extension of K. But an nth root of unity
generates a separable extension of K when the characteristic does not divide
n, so we conclude that О¶ в€€ K.)

COROLLARY 3.13
Let E be an elliptic curve deп¬Ѓned over Q. Then E[n] вЉ† E(Q) for n в‰Ґ 3.

If E[n] вЉ† E(Q), then Вµn вЉ‚ Q, which is not the case when n в‰Ґ 3.
PROOF

REMARK 3.14 When n = 2, it is possible to have E вЉ† E(Q). For
example, if E is given by y 2 = x(x в€’ 1)(x + 1), then
E = {в€ћ, (0, 0), (1, 0), (в€’1, 0)}.
If n = 3, 4, 5, 6, 7, 8, 9, 10, 12, there are elliptic curves E deп¬Ѓned over Q that
have points of order n with rational coordinates. However, the corollary says
that it is not possible for all points of order n to have rational coordinates for
these n. The torsion subgroups of elliptic curves over Q will be discussed in
Chapter 8.

В© 2008 by Taylor & Francis Group, LLC
89
SECTION 3.3 THE WEIL PAIRING

We now use the Weil pairing to deduce two propositions that will be used in
the proof of HasseвЂ™s theorem in Chapter 4. Recall that if О± is an endomorphism
ab
of E, then we obtain a matrix О±n = with entries in Zn , describing the
cd
action of О± on a basis {T1 , T2 } of E[n].

PROPOSITION 3.15
Let О± be an endomorphism of an elliptic curve E deп¬Ѓned over a п¬Ѓeld K.
Let n be a positive integer not divisible by the characteristic of K. Then
det(О±n ) в‰Ў deg(О±) (mod n).

PROOF By Corollary 3.10, О¶ = en (T1 , T2 ) is a primitive nth root of unity.
By part (6) of Theorem 3.9, we have

О¶ deg(О±) = en (О±(T1 ), О±(T2 )) = en (aT1 + cT2 , bT1 + dT2 )
= en (T1 , T1 )ab en (T1 , T2 )ad en (T2 , T1 )cb en (T2 , T2 )cd

by the properties of the Weil pairing. Since О¶ is a primitive nth root of unity,
deg(О±) в‰Ў ad в€’ bc (mod n).

As weвЂ™ll see in the proof of the next result, Proposition 3.15 allows us to
reduce questions about the degree to calculations with matrices. Both Propo-
sition 3.15 and Proposition 3.16 hold for all endomorphisms, since part (6)
of Theorem 3.9 holds in general. However, we prove part (6) only for sepa-
rable endomorphisms and for the Frobenius map, which is suп¬ѓcient for our
purposes. WeвЂ™ll state Proposition 3.16 in general, and the proof is suп¬ѓcient
for separable endomorphisms and for all endomorphisms of the form r + sП†q
with arbitrary integers r, s.
Let О± and ОІ be endomorphisms of E and let a, b be integers. The endomor-
phism aО± + bОІ is deп¬Ѓned by

(aО± + bОІ)(P ) = aО±(P ) + bОІ(P ).

Here aО±(P ) means multiplication on E of О±(P ) by the integer a. The result
is then added on E to bОІ(P ). This process can all be described by rational
functions, since this is true for each of the individual steps. Therefore aО± + bОІ
is an endomorphism.

PROPOSITION 3.16

deg(aО± + bОІ) = a2 deg О± + b2 deg ОІ + ab(deg(О± + ОІ) в€’ deg О± в€’ deg ОІ).

В© 2008 by Taylor & Francis Group, LLC
90 CHAPTER 3 TORSION POINTS

PROOF Let n be any integer not divisible by the characteristic of K.
Represent О± and ОІ by matrices О±n and ОІn (with respect to some basis of
E[n]). Then aО±n + bОІn gives the action of aО± + bОІ on E[n]. A straightforward
calculation yields

det(aО±n + bОІn ) = a2 det О±n + b2 det ОІn + ab(det(О±n + ОІn ) в€’ det О±n в€’ det ОІn )

for any matrices О±n and ОІn (see Exercise 3.4). Therefore

deg(aО± + bОІ) в‰Ў
a2 deg О± + b2 deg ОІ + ab(deg(О± + ОІ) в€’ deg О± в€’ deg ОІ) (mod n).

Since this holds for inп¬Ѓnitely many n, it must be an equality.

3.4 The Tate-Lichtenbaum Pairing
Starting from the Weil pairing, it is possible to deп¬Ѓne a pairing that can be
used in cases where the full n-torsion is not available, so the Weil pairing does
not apply directly. The approach used in this section was inspired by work of
Schaefer .

THEOREM 3.17
Let E be an elliptic curve over Fq . Let n be an integer such that n|q в€’ 1.
Denote by E(Fq )[n] the elements of E(Fq ) of order dividing n, and let Вµn =
{x в€€ Fq | xn = 1}. Let P в€€ E(Fq )[n] and Q в€€ E(Fq ) and choose R в€€ E(Fq )
satisfying nR = Q. Denote by en the nth Weil pairing and by П† = П†q the qth
power Frobenius endomorphism. Deп¬Ѓne

П„n (P, Q) = en (P, R в€’ П†(R)).

Then
П„n : E(Fq )[n] Г— E(Fq )/nE(Fq ) в€’в†’ Вµn
is a well-deп¬Ѓned nondegenerate bilinear pairing.

The pairing of the theorem is called the modiп¬Ѓed Tate-Lichtenbaum
pairing. The original Tate-Lichtenbaum pairing is obtained by taking
the nth root of П„n , thus obtaining a pairing

: E(Fq )[n] Г— E(Fq )/nE(Fq ) в€’в†’ FГ— /(FГ— )n .
В·, В· n q q

The pairing П„n is better suited for computations since it gives a deп¬Ѓnite answer,
rather than a coset in FГ— mod nth powers. These pairings can be computed
q

В© 2008 by Taylor & Francis Group, LLC
91
SECTION 3.4 THE TATE-LICHTENBAUM PAIRING

quickly (using at most a constant times log q point additions on E). See
Section 11.4.
Technically, we should write П„n (P, Q) as П„n (P, Q+nE(Fq )), since an element
of E(Fq )/nE(Fq ) has the form Q + nE(Fq ). However, weвЂ™ll simply write
П„n (P, Q) and similarly for P, Q n . The fact that П„n is nondegenerate means
that if П„n (P, Q) = 1 for all Q then P = в€ћ, and if П„n (P, Q) = 1 for all P then
Q в€€ nE(Fq ). Bilinearity means that

П„n (P1 + P1 , Q) = П„n (P1 , Q)П„n (P2 , Q)

and
П„n (P, Q1 + Q2 ) = П„n (P, Q1 )П„n (P, Q2 ).

PROOF We now prove the theorem. First, we need to show that П„n (P, Q)
is deп¬Ѓned and is independent of the choice of R. Since nR = Q в€€ E(Fq ), we
have
в€ћ = Q в€’ П†(Q) = n (R в€’ П†R) ,
so R в€’ П†R в€€ E[n] (to lower the number of parentheses, we often write П†R
instead of П†(R)). Since P в€€ E[n], too, the Weil pairing en (P, R в€’ П†R) is
deп¬Ѓned. Suppose that nR = Q gives another choice of R. Let T = R в€’ R.
Then nT = Q в€’ Q = в€ћ, so T в€€ E[n]. Therefore,

en (P, R в€’ П†R ) = en (P, R в€’ П†R + T в€’ П†T )
= en (P, R в€’ П†R)en (P, T )/en (P, П†T ).

But P = П†P , since P в€€ E(Fq ), so

en (P, П†T ) = en (П†P, П†T ) = П† (en (P, T )) = en (P, T ),

since en (P, T ) в€€ Вµn вЉ‚ Fq . Therefore,

en (P, R в€’ П†R ) = en (P, R в€’ П†R),

so П„n does not depend on the choice of R.
Since Q is actually a representative of a coset in E(Fq )/nE(Fq ), we need
to show that the value of П„n depends only on the coset, not on the particular
choice of representative. Therefore, suppose Q в€’ Q = nU в€€ nE(Fq ). Let
nR = Q and let R = R + U . Then nR = Q . We have

en (P, R в€’ П†R ) = en (P, R в€’ П†R + U в€’ П†U ) = en (P, R в€’ П†R),

since U = П†U for U в€€ E(Fq ). Therefore, the value does not depend on the
choice of coset representative. This completes the proof that П„n is well deп¬Ѓned.
The fact that П„n (P, Q) is bilinear in P follows immediately from the cor-
responding fact for en . For bilinearity in Q, suppose that nR1 = Q1 and

В© 2008 by Taylor & Francis Group, LLC
92 CHAPTER 3 TORSION POINTS

nR2 = Q2 . Then n(R1 + R2 ) = Q1 + Q2 , so

П„n (P, Q1 + Q2 ) = en (P, R1 + R2 в€’ П†R1 в€’ П†R2 )
= en (P, R1 в€’ П†R1 )en (P, R2 в€’ П†R2 )
= П„n (P, Q1 )П„n (P, Q2 ).

It remains to prove the nondegeneracy. This we postpone to Section 11.7.

The Tate-Lichtenbaum pairing can be used in some situations where the
Weil pairing does not apply. The Weil pairing needs E[n] вЉ† E(Fq ), which
implies that Вµn вЉ† FГ— , by Corollary 3.11. The Tate-Lichtenbaum pairing
q
requires that Вµn вЉ† FГ— , but only needs a point of order n, rather than all
q
of E[n], to be in E(Fq ). In fact, it doesnвЂ™t even need a point of order n. If
E(Fq )[n] is trivial, for example, then we have a pairing between two trivial
groups.

Exercises
3.1 Let E be the elliptic curve y 2 = x3 + 1 mod 5.

(a) Compute the division polynomial П€3 (x).
(b) Show that gcd(x5 в€’ x, П€3 (x)) = x.
(c) Use the result of part (b) to show that the 3-torsion points in E(F5 )
are {в€ћ, (0, 1), (0, в€’1)}.

Z3 вЉ• Z3 .
3.2 Let E be an elliptic curve in characteristic 2. Show that E
(Hint: Use the formulas at the end of Section 2.8.)

3.3 Let E be an elliptic curve over a п¬Ѓeld of characteristic not 2. Let E =
{в€ћ, P1 , P2 , P3 }. Show that e2 (Pi , Pj ) = в€’1 whenever i = j.

wx Лњ
3.4 Let M and N be 2 Г— 2 matrices with N = . Deп¬Ѓne N =
yz
z в€’x
в€’y w
Лњ
(a) Show that Trace(M N ) = det(M + N ) в€’ det(M ) в€’ det(N ).
(b) Use (a) to show that

det(aM + bN ) в€’ a2 det M в€’ b2 det N
= ab(det(M + N ) в€’ det M в€’ det N )

В© 2008 by Taylor & Francis Group, LLC
93
EXERCISES

for all scalars a, b. This is the relation used in the proof of Propo-
sition 3.16.
3.5 Show that part (6) of Theorem 3.9 holds when О± is the endomorphism
given by multiplication by an integer m.
3.6 Let E be an elliptic curve over a п¬Ѓeld K and let P be a point of order
n (where n is not divisible by the characteristic of the п¬Ѓeld K). Let
Q в€€ E[n]. Show that there exists an integer k such that Q = kP if and
only if en (P, Q) = 1.
3.7 Write the equation of the elliptic curve E as

F (x, y, z) = y 2 z в€’ x3 в€’ Axz 2 в€’ Bz 3 = 0.

Show that a point P on E is in E if and only if
вЋ› вЋћ
Fxx Fxy Fxz
det вЋќ Fyx Fyy Fyz вЋ  = 0
Fzx Fzy Fzz

at the point P , where Fab denotes the 2nd partial derivative with respect
to a, b. The determinant is called the Hessian. For a curve in P2 deп¬Ѓned
by an equation F = 0, a point where the Hessian is zero is called a п¬‚ex
of the curve.
3.8 The division polynomials П€n were deп¬Ѓned for n в‰Ґ 0. Show that if we
let П€в€’n = в€’П€n , then the recurrence relations preceding Lemma 3.3,
which are stated only for m в‰Ґ 2, hold for all integers m. (Note that this
requires verifying the relations for m в‰¤ в€’2 and for m = в€’1, 0, 1.)

В© 2008 by Taylor & Francis Group, LLC