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[2]. 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[2] = {∞, (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[2] = {∞, (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[2] = {∞}.

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[2] Z2 • Z2 .
If the characteristic of K is 2, then

E[2] 0 or Z2 .

Now let™s look at E[3]. 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[3], we see that E[3] is a group of order 9 in which
every element is 3-torsion. It follows that

Z3 • Z3 .
E[3]




© 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[3] = {∞} 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[3] has order 3, so E[3] 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[2] = {∞, (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[2], 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 [38].)

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[2] ⊆ E(Q). For
example, if E is given by y 2 = x(x ’ 1)(x + 1), then
E[2] = {∞, (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
= ζ ad’bc ,

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 [96].

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[3]
(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[2] =
{∞, 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
(this is the adjoint matrix).
’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[3] 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