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