Isogenies

Isogenies, which are homomorphisms between elliptic curves, play a funda-

mental role in the theory of elliptic curves since they allow us to relate one

elliptic curve to another. In the ¬rst section, we describe the analytic theory

over the complex numbers. In subsequent sections, we obtain similar results

in the algebraic setting. Finally, we sketch how isogenies can be used to count

points on elliptic curves over ¬nite ¬elds.

12.1 The Complex Theory

Let E1 = C/L1 and E2 = C/L2 be elliptic curves over C. Let ± ∈ C be

such that ±L1 ⊆ L2 . Then

[±] : E1 ’’ E2

z ’’ ±z

gives a homomorphism from E1 to E2 (we need ±L1 ⊆ L2 to make the map

well-de¬ned). A map of the form [±] with ± = 0 is called an isogeny from

E1 to E2 . If there exists an isogeny from E1 to E2 , we say that E1 and E2

are isogenous.

LEMMA 12.1

If ± = 0, then ±L1 is of ¬nite index in L2 .

(k) (k)

Let {ω1 , ω2 } be a basis for Lk , for k = 1, 2. Write

PROOF

(1) (2) (2)

±ωi = ai1 ω1 + ai2 ω2

with aij ∈ Z. If det(aij ) = 0 then (a11 , a12 ) is a rational multiple of (a21 , a22 ),

(1) (1)

which implies that ±ω1 is a rational multiple of ±ω2 . This is impossible

(1) (1)

since ω1 and ω2 are linearly independent over R.

381

© 2008 by Taylor & Francis Group, LLC

382 CHAPTER 12 ISOGENIES

(k)

Regard each ωi as a two-dimensional vector over R. Then the area of the

(k) (k)

fundamental parallelogram of Lk is | det(ω1 , ω2 )|. Since

(1) (1) (2) (2)

det ±ω1 , ±ω2 = det(aij ) det ω1 , ω2 ,

the index of ±L1 in L2 , which is the ratio of the areas of the fundamental

parallelograms, equals | det(aij )|.

REMARK 12.2 A potential source of confusion is the following. Suppose

a lattice L1 is contained in L2 , so L2 is a larger lattice than L1 . Let F1 and F2

be fundamental parallelograms for these lattices. Then F2 is smaller than F1 .

For example, let L1 = 2Z + 2iZ and L2 = Z + iZ. Then L1 ‚ L2 . The unit

square is a fundamental parallelogram for L2 , while the square with corners

at 0, 2, 2i, 2 + 2i is a fundamental parallelogram for L1 .

De¬ne the degree of [±] to be the index [L2 : ±L1 ]. If ± = 0, de¬ne

the degree to be 0. If N is the degree, we say that C/L1 and C/L2 are N -

isogenous. The existence of the dual isogeny, de¬ned below, shows that if E1

and E2 are N -isogenous, then E2 and E1 are N -isogenous, so this relation is

symmetric.

PROPOSITION 12.3

If ± = 0, then #Ker([±]) = deg([±]).

Let z ∈ C. Then [±](z) = 0 ⇐’ ±z ∈ L2 , so

PROOF

Ker([±]) = ±’1 L2 /L1 L2 /±L1 ,

where the isomorphism is given by multiplication by ±. Therefore, the order

of the kernel is the index, which is the degree.

If Ker([±]) = ±’1 L2 /L1 is cyclic, we say that [±] is a cyclic isogeny.

In general, Ker([±]) is a ¬nite abelian group with at most two generators

(coming from the generators of L2 ), so it has the form Zn1 • Zn2 with n1 |n2

(see Appendix B). Therefore, the isogeny equals multiplication by n1 on E1

composed with a cyclic isogeny whose kernel has order n2 /n1 (Exercise 12.2).

Let ± = 0 and let N = deg([±]). De¬ne the dual isogeny

[±] : C/L2 ’’ C/L1

to be the map given by multiplication by N/±. We need to show this is well

de¬ned: Since N = [L2 : ±L1 ], we have N L2 ⊆ ±L1 . Therefore, (N/±)L2 ⊆

L1 , as desired.

© 2008 by Taylor & Francis Group, LLC

383

SECTION 12.1 THE COMPLEX THEORY

We have the fundamental relation:

[±] —¦ [±] = deg([±]),

where the integer deg([±]) denotes integer multiplication on C/L1 . It is easy

to show (see Exercise 12.3) that

[±] = [±]

and that

[±] —¦ [±] = deg([±]) = deg([±]),

which is integer multiplication on C/L2 .

A situation that arises frequently is when ± = 1. This means that we have

L1 ⊆ L2 and the isogeny is simply the map

z mod L1 ’’ z mod L2 .

The kernel is L2 /L1 . An arbitrary isogeny [±] can be reduced to this situation

by composing with the isomorphism C/L2 ’ C/±’1 L2 given by multiplica-

tion by ±’1 .

PROPOSITION 12.4

Let C ‚ E1 = C/L be a ¬nite subgroup. Then there exist an elliptic curve

E2 = C/L2 and an isogeny from E1 to E2 whose kernel is C.

PROOF C can be written as L2 /L1 for some subgroup L2 of C containing

L1 . If N is the order of C, then N L2 ⊆ L1 , so L1 ⊆ L2 ⊆ (1/N )L1 . By the

discussion following Theorem B.5 in Appendix B, L2 is a lattice. Therefore,

C/L1 ’ C/L2 is the desired isogeny.

Given two elliptic curves and an integer N , there is a way to decide if

they are N -isogenous. Recall the modular polynomial ¦N (X, Y ) (see Theo-

rem 10.15 and page 324), which satis¬es

(j(„1 ) ’ j(S(„2 ))) ,

¦N (j(„1 ), j(„2 )) =

S∈SN

ab

where SN is the set of matrices with a, b, d positive integers satisfying

0d

ad = N and 0 ¤ b < d.

THEOREM 12.5

Let N be a positive integer and let ¦N (X, Y ) be the N th modular polynomial,

as in Theorem 10.15. Let Ei = C/Li have j-invariant ji for i = 1, 2. Then

E1 is N -isogenous to E2 if and only if ¦N (j1 , j2 ) = 0.

© 2008 by Taylor & Francis Group, LLC

384 CHAPTER 12 ISOGENIES

PROOF Write jk = j(„k ) for some „k . Suppose ¦N (j1 , j2 ) = 0. Then

ab

∈ SN . By Corollary 9.19, there

j(„1 ) = j(S(„2 )) for some S =

0d

st

∈ SL2 (Z) such that (s„1 + t)/(u„1 + v) = S(„2 ). Writing

exists M =

uv

„1 = ω1 /ω2 for some basis {ω1 , ω2 } of L1 , we see that (sω1 +tω2 )/(uω1 +vω2 ) =

S(„2 ). But {sω1 + tω2 , uω1 + vω2 } is another basis for L1 since M ∈ SL2 (Z).

(i) (i)

We conclude that there exist bases {ω1 , ω2 } of Li , for i = 1, 2, such that

(1) (2) (2)

ω1 aω1 + bω2

= S(„2 ) = .

(1) (2)

ω2 dω2

(2) (2) (1) (1) (2) (1)

Let ± = (aω1 + bω2 )/ω1 . Then ±ω2 = dω2 . Therefore ±ωi , for

i = 1, 2, is a linear combination with integer coe¬cients of the basis elements

of L2 , so ±L1 ⊆ L2 . As we saw in the proof of Lemma 12.1, the index

ab

[L2 : ±L1 ] is the determinant of , which is N . Therefore, [±] gives an

0d

N -isogeny from C/L1 to C/L2 .

Conversely, suppose that there is an N -isogeny [±] from C/L1 to C/L2 .

Write

(1) (2)

ω1 ω1

± = (aij ) ,

(1) (2)

ω2 ω2

as in Lemma 12.1. By Lemma 10.10, we can write

a11 a12 b11 b12 ab

=

a21 a22 b21 b22 0d

with (bij ) ∈ SL2 (Z). Let

(1)

ω1 ω1

’1

= (bij ) .

(1)

ω2 ω2

Then

(2)

ab ω1

ω1

± = .

(2)

ω2 0d ω2

Therefore,

(2) (2)

ω1 aω1 + bω2 a„2 + b

= = ,

(2)

ω2 d

dω2

(2) (2)

where „2 = ω1 /ω2 . The fact that (bij ) ∈ SL2 (Z) implies that {ω1 , ω2 } is a

basis of L1 . Since j1 = j(ω1 /ω2 ), we obtain

ab

j1 = j(S(„2 )), where S = .

0d

© 2008 by Taylor & Francis Group, LLC

385

SECTION 12.1 THE COMPLEX THEORY

Therefore, ¦N (j1 , j2 ) = 0.

Example 12.1

The curve E1 : y 2 = 4(x3 ’ 2x + 1) has j-invariant j1 = 55296/5 and the curve

E2 : y 2 = 4(x3 ’ 7x ’ 6) has j2 = 148176/25. A calculation (the polynomial

¦2 is given on page 329) shows that

55296 148176

, = 0,

¦2

5 25

so there is a 2-isogeny from E1 to E2 . The AGM method (Section 9.4.1)

allows us to compute the period lattices:

L1 = Z(2.01890581997842 . . . )i + Z(2.96882494684477 . . . )

L2 = Z(2.01890581997842 . . . )i + Z(1.48441247342238 . . . ).

The real period for E1 is twice the real period for E2 , and the complex periods

are equal. The map C/L1 ’ C/L2 given by z ’ z gives the 2-isogeny. There

is also a 2-isogeny C/L2 ’ C/L1 given by z ’ 2z. We have the factorization

148176 132304644 55296 236276

x’ x’ x’

¦2 x, = .

25 5 5 125

Therefore, E2 is also isogenous to elliptic curves with j-invariants 132304644/5

and 236276/125.

We now prove that all nonconstant maps between elliptic curves over C are

linear. This has the interesting consequence that a nonconstant map taking

0 to 0 is of the form [±], hence is a homomorphism.

THEOREM 12.6

Let E1 = C/L1 and E2 = C/L2 be elliptic curves over C. Suppose that

f : E1 ’ E2 is an analytic map (that is, f can be expressed as a power series

in a neighborhood of each point of E1 ). Then there exist ±, β ∈ C such that

f (z mod L1 ) = ±z + β mod L2

for all z ∈ C. In particular, if f (0 mod L1 ) = 0 mod L2 and f is not the

0-map, then f is an isogeny.

˜

We can lift f to a continuous map f : C ’ C satisfying

PROOF

˜

f (z mod L1 ) = f (z) mod L2

˜

for all z ∈ C (see Exercise 12.13). Moreover, f can be expressed as a power

series in the neighborhood of each point in C (this is the de¬nition of f being

© 2008 by Taylor & Francis Group, LLC

386 CHAPTER 12 ISOGENIES

an analytic map). Let ω ∈ L1 . Then the function

˜ ˜

f (z + ω) ’ f (z)

reduces to 0 mod L2 . Since it is continuous and takes values in the discrete

˜ ˜

set L2 , it is constant. Therefore, its derivative is 0, so f (z + ω) = f (z) for

˜

all z. This means that f is a holomorphic doubly periodic function, hence

˜

constant, by Theorem 9.1. Therefore, f (z) = ±z + β for some ±, β, as desired.

In anticipation of the algebraic situation, and recalling that endomorphisms

of elliptic curves are given by rational functions, we prove the following.

PROPOSITION 12.7

Let E1 = C/L1 and E2 = C/L2 be elliptic curves over C, let „˜i (z) be the

Weierstrass „˜-function for Ei , and let [±] be an isogeny from E1 to E2 . Then

there are rational functions R1 (x), R2 (x) such that

„˜2 (±z) = R1 („˜1 (z)) , „˜2 (±z) = „˜1 (z)R2 („˜1 (z)) .

PROOF We have ±L1 ⊆ L2 . Let f (z) = „˜2 (±z). Let ω ∈ L1 . Then

±ω ∈ L2 , so

f (z + ω) = „˜2 (±z + ±ω) = „˜2 (±z) = f (z)

for all z. Therefore, z ’ „˜2 (±z) is a rational function of „˜1 and „˜1 by

Theorem 9.3. In fact, the end of the proof of Theorem 9.3 shows that, since

„˜2 (±z) is an even function, it is a rational function of „˜1 (z). Di¬erentiation

yields the statement about „˜2 (±z).

2

Recall that z mod L1 corresponds to („˜1 (z), „˜1 (z) ) on the curve E1 : y1 =

4x3 ’ g2 x1 ’ g3 . The proposition says that [±] : E1 ’ E2 corresponds to

1

(x1 , y1 ) ’’ (x2 , y2 ) = (R1 (x1 ), y1 R2 (x1 )) .

12.2 The Algebraic Theory

Let E1 : y1 = x3 + A1 x1 + B1 and E2 : y2 = x3 + A2 x2 + B2 be elliptic

2 2

1 2

curves over a ¬eld K (later we will also work with generalized Weierstrass

equations). An isogeny from E1 to E2 is a nonconstant homomorphism

± : E1 (K) ’ E2 (K) that is given by rational functions. This means that

±(P + Q) = ±(P ) + ±(Q) for all P, Q ∈ E1 (K) and that there are rational

© 2008 by Taylor & Francis Group, LLC

387

SECTION 12.2 THE ALGEBRAIC THEORY

functions R1 , R2 such that if ±(x1 , y1 ) = (x2 , y2 ), then

x2 = R1 (x1 , y1 ), y2 = R2 (x1 , y1 )

for all but ¬nitely many (x1 , y1 ) ∈ E1 (K). The technicalities for the points

where R1 and R2 are not de¬ned are dealt with in the same way as for

endomorphisms, as in Section 2.9. In fact, when E1 = E2 , an isogeny is a

nonzero endomorphism.

As in Section 2.9, we may write ± in the form

(x2 , y2 ) = ±(x1 , y1 ) = (r1 (x1 ), y1 r2 (x1 )) ,

where r1 , r2 are rational functions. If the coe¬cients of r1 , r2 lie in K, we say

that ± is de¬ned over K. Write

r1 (x) = p(x)/q(x)

with polynomials p(x) and q(x) that do not have a common factor. De¬ne

the degree of ± to be

deg(±) = Max{deg p(x), deg q(x)}.

If the derivative r1 (x) is not identically 0, we say that ± is separable.

PROPOSITION 12.8

Let ± : E1 ’ E2 be an isogeny. If ± is separable, then

deg ± = #Ker(±).

If ± is not separable, then

deg ± > #Ker(±).

In particular, the kernel of an isogeny is a ¬nite subgroup of E1 (K).

PROOF The proof is identical to the proof of Proposition 2.21.

PROPOSITION 12.9

Let ± : E1 ’ E2 be an isogeny. Then ± : E1 (K) ’ E2 (K) is surjective.

PROOF The proof is identical to the proof of Theorem 2.22.

Example 12.2

Let p be an odd prime, let A1 , B1 be in a ¬eld of characteristic p, and let

E1 : y1 = x3 + A1 x1 + B1 and E2 : y2 = x3 + Ap x2 + B1 . De¬ne φ by

p

2 2

1 2 1

(x2 , y2 ) = φ(x1 , y1 ) = (xp , y1 ).

p

1

© 2008 by Taylor & Francis Group, LLC

388 CHAPTER 12 ISOGENIES

Suppose x1 , y1 ∈ K satisfy y1 = x3 + A1 x1 + B1 . Raising this equation to the

2

1

p-th power yields

(y1 )2 = (xp )3 + Ap (xp ) + B1 .

p p

1 11

Since x2 = xp and y2 = y1 , this means that φ maps E1 (K) to E2 (K). It is

p

1

easy to see that φ is a homomorphism (as in Lemma 2.20). We have

r1 (x) = xp r2 (x) = (y 2 )(p’1)/2 = (x3 + A1 x + B1 )(p’1)/2 .

and

Therefore, deg(φ) = deg r1 = p. If Q = ∞ is a point of E1 , then φ(Q) = ∞,

so Ker(φ) is trivial. The fact that the degree is larger than the cardinality of

the kernel corresponds to the fact that φ is not separable.

Example 12.3

Let E1 : y1 = x3 +ax2 +bx1 be an elliptic curve over some ¬eld of characteristic

2

1 1

not 2. We require b = 0 and a2 ’ 4b = 0 in order to have E1 nonsingular.

Then (0, 0) is a point of order 2. Let E2 be the elliptic curve y2 = x3 ’ 2ax2 +

2

2 2

(a2 ’ 4b)x2 . De¬ne ± by

y1 y1 (x2 ’ b)

2

1

(x2 , y2 ) = ±(x1 , y1 ) = 2, .

x2

x1 1

It is straightforward to check that ± maps points of E1 (K) to points of E2 (K).

It is more di¬cult to show that ± is a homomorphism. However, this fact

follows from Theorem 12.10 below. (We need to verify that ±(∞) = ∞. For

this, see Exercise 12.4.)

We have

x3 + ax2 + bx x2 + ax + b

r1 (x) = = ,

x2 x

so deg ± = 2 and ± is separable. This means that there are two points in the

kernel. Writing r1 (x) = x + a + (b/x), we see that these two points must be

∞ and (0, 0), since all other points have ¬nite images (for another proof that

±(0, 0) = ∞, see Exercise 12.5).

THEOREM 12.10

Let E1 and E2 be elliptic curves over a ¬eld K. Let ± : E1 (K) ’ E2 (K)

be a nonconstant map given by rational functions. If ±(∞) = ∞, then ± is a

homomorphism, and therefore an isogeny.

PROOF Recall that, by Corollary 11.4, there are group isomorphisms

ψi : Ei (K) ’’ Div0 (Ei )/(principal divisors)

given by P ’ [P ] ’ [∞]. De¬ne ±— : Div0 (E1 ) ’ Div0 (E2 ) by

bj [Pj ] ’’

±— : bj [±(Pj )].

© 2008 by Taylor & Francis Group, LLC

389

SECTION 12.2 THE ALGEBRAIC THEORY

Clearly, ±— is a group homomorphism.

LEMMA 12.11

±— maps principal divisors to principal divisors.

PROOF Writing (x2 , y2 ) = ±(x1 , y1 ), where (xi , yi ) are coordinates for

Ei , allows us to regard K(x2 , y2 ) as a sub¬eld of K(x1 , y1 ) (see the proof

of Proposition 12.12). The norm map for this extension maps elements of

K(x1 , y1 )— to elements of K(x2 , y2 )— , and yields a map from principal divisors

on E1 to principal divisors on E2 . The main part of the proof of the lemma is

showing that this norm map is the same as the map ±— on principal divisors.

For this, see [43, Prop. 1.4].

Therefore, ±— gives a well-de¬ned map

±— : Div0 (E1 )/(principal divisors) ’’ Div0 (E2 )/(principal divisors).

If P ∈ E1 (K), then

±— (ψ1 (P )) = ±— ([P ] ’ [∞]) = [±(P )] ’ [∞] = ψ2 (±(P )).

Therefore,

’1

± = ψ2 —¦ ±— —¦ ψ1 .

Since all three maps on the right are homomorphisms, so is ±.

The following tells us that an elliptic curve isogenous to an elliptic curve E

is essentially uniquely determined by the kernel of the isogeny to it. This may

seem obvious from the viewpoint of group theory since the group of points

on the isogenous curve is isomorphic to E(K)/C, where C is the kernel of

the isogeny. But we are asking for more: we want the uniqueness of the

curve as an algebraic variety. We say that two elliptic curves E2 , E3 are

isomorphic if there are group homomorphisms β : E2 (K) ’ E3 (K) and

γ : E3 (K) ’ E2 (K) such that β and γ are given by rational functions and

such that γ —¦ β = id on E2 and β —¦ γ = id on E3 .

PROPOSITION 12.12

Let E1 , E2 , E3 be elliptic curves over a ¬eld K and suppose that there exist

separable isogenies ±2 : E1 ’ E2 and ±3 : E1 ’ E3 de¬ned over K. If

Ker ±2 = Ker ±3 , then E2 is isomorphic to E3 over K. In fact, there is an

isomorphism β : E2 ’ E3 such that β —¦ ±2 = ±3 .

PROOF This proof will use some concepts from ¬eld theory and Galois

theory. It may be skipped by readers unfamiliar with these subjects.

© 2008 by Taylor & Francis Group, LLC

390 CHAPTER 12 ISOGENIES

Assume for simplicity that the elliptic curves are in Weierstrass form: Ei :

2

= x3 +Ai xi +Bi . The isogeny ±2 can be described by (x2 , y2 ) = ±2 (x1 , y1 ) =

yi i

(r1 (x1 ), y1 r2 (x1 )), where r1 and r2 are rational functions with coe¬cients in

the ¬eld K. This allows us to regard K(x2 , y2 ) as a sub¬eld of K(x1 , y1 ).

Write r1 (x1 ) = p(x1 )/q(x1 ), where p and q are polynomials with no common

factors. Then p(T ) ’ x2 q(T ) ∈ K(x2 )[T ] is irreducible of degree N = deg ±2

(see Exercise 12.7). Therefore, the extension K(x1 )/K(x2 ) has degree N .

x3 + Ai xi + Bi ∈ K(xi ). Therefore, [K(xi , yi ) :

By Lemma 11.5, yi = i

K(xi )] = 2. It follows that

2[K(x1 , y1 ) : K(x2 , y2 )] = [K(x1 , y1 ) : K(x2 , y2 )][K(x2 , y2 ) : K(x2 )]

= [K(x1 , y1 ) : K(x1 )][K(x1 ) : K(x2 )] = 2N,

so [K(x1 , y1 ) : K(x2 , y2 )] = N .

Let Q be in the kernel of ±2 . Translation by Q gives a map

σQ : (x1 , y1 ) ’ (x1 , y1 ) + Q = (f (x1 , y1 ), g(x1 , y1 )) .

This is an automorphism of K(x1 , y1 ) (see Exercise 12.9). Since

σQ (x2 , y2 ) = σQ (±2 (x1 , y1 )) = ±2 ((x1 , y1 ) + Q) = ±2 (x1 , y1 ) = (x2 , y2 ),

this automorphism acts as the identity on the ¬eld K(x2 , y2 ). A result from

¬eld theory says that if G is a ¬nite group of automorphisms of a ¬eld L,

then the sub¬eld of elements ¬xed by G is of degree #G below L (see, for

example, [71]). If ±2 is separable, there are N (= deg ±2 ) automorphisms given

by translation by elements of the kernel of ±2 , so the ¬xed ¬eld of this group

is of degree N below K(x1 , y1 ). Since K(x2 , y2 ) is contained in this ¬xed ¬eld,

and [K(x1 , y1 ) : K(x2 , y2 )] = N , the ¬xed ¬eld is exactly K(x2 , y2 ).

The same analysis applies to ±3 . If ±2 and ±3 are separable with the same

kernel, then K(x2 , y2 ) and K(x3 , y3 ) are the ¬xed ¬eld of the same group of

automorphisms, hence

K(x2 , y2 ) = K(x3 , y3 ).

Therefore, x2 , y2 are rational functions of x3 , y3 , and x3 , y3 are rational func-

tions of x2 , y2 . Write

x2 = R1 (x3 , y3 ), y2 = R2 (x3 , y3 )

for rational functions R1 , R2 . Then

γ : (x3 , y3 ) ’ (x2 , y2 ) = (R1 (x3 , y3 ), R2 (x3 , y3 ))

gives a map E3 ’ E2 . Similarly, there exists β : E2 ’ E3 , and γ—¦β = id on E2

and β —¦ γ = id on E3 . By translating the images of β and γ (that is, change

β to β ’ β(∞), and similarly for γ), we may assume that β(∞) = ∞ and

© 2008 by Taylor & Francis Group, LLC

391

SECTION 12.2 THE ALGEBRAIC THEORY

γ(∞) = ∞. By Theorem 12.10, these maps are homomorphisms. Therefore,

β is an isomorphism, so E2 and E3 are isomorphic, as claimed. Moreover,

β —¦ ±2 (x1 , y1 ) = β(x2 , y2 ) = (x3 , y3 ) = ±3 (x1 , y1 ),

so β —¦ ±2 = ±3 .

REMARK 12.13 If ±2 and ±3 are de¬ned over K, then it is possible to

show that E2 and E3 are isomorphic over K. See [109, Exercise 3.13].

A very important property of isogenies is the existence of dual isogenies.

We already proved this in the case of elliptic curves over C. In the following,

we treat elliptic curves over arbitrary ¬elds.

THEOREM 12.14

Let ± : E1 ’ E2 be an isogeny of elliptic curves. Then there exists a dual

isogeny ± : E2 ’ E1 such that ± —¦ ± is multiplication by deg ± on E1 .

PROOF We give the proof only in the case that deg ± is not divisible

by the characteristic of the ¬eld K. The proof in the general case involves

working with inseparable extensions of ¬elds. See [109].

Let N = deg ±. Then Ker(±) ‚ E1 [N ], and ±(E1 [N ]) is a subgroup of

E1 of order N . We show in Theorem 12.16 that there exists an isogeny

±2 : E2 ’ E3 , for some E3 , such that Ker(±3 ) = ±(E1 [N ]). Then ±2 —¦ ± has

kernel equal to E1 [N ]. The map E1 ’ E1 given by multiplication by N has

the same kernel. By Proposition 12.12, there is an isomorphism β : E3 ’ E1

such that β —¦ ±2 —¦ ± is multiplication by N . Let ± = β —¦ ±2 .

The map ± is unique, its degree is deg ±, and ± —¦ ± equals multiplication

by deg(±) on E2 . See Exercise 12.10.

If ± and β are isogenies from E1 to E2 , then ±+β is de¬ned by (±+β)(P ) =

±(P )+β(P ). If ± = ’β, this is an isogeny. It can be shown that ± + β = ±+β.

See [109].

REMARK 12.15 There is an inseparable isogeny for which the dual

isogeny can be constructed easily. If E is an elliptic curve over the ¬nite

¬eld Fq , then the qth power Frobenius endomorphism can be regarded as an

isogeny of degree q from E to itself. We know that φ2 ’ aφ + q = 0 for some

integer a. Therefore,

(a ’ φ) —¦ φ = q = deg φ,

so φ = a ’ φ is the dual isogeny for φ.

© 2008 by Taylor & Francis Group, LLC

392 CHAPTER 12 ISOGENIES

12.3 V´lu™s Formulas

e

We now consider the algebraic version of Proposition 12.4. Since it is often

convenient to translate a point in the kernel of an isogeny to the origin, for

example, we work with the general Weierstrass form. The explicit formulas

given in the theorem are due to V´lu [123].

e

THEOREM 12.16

Let E be an elliptic curve given by the generalized Weierstrass equation

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 ,

with all ai in some ¬eld K. Let C be a ¬nite subgroup of E(K). Then there

exists an elliptic curve E2 and a separable isogeny ± from E to E2 such that

C = Ker ±.

For a point Q = (xQ , yQ ) ∈ C with Q = ∞, de¬ne

gQ = 3x2 + 2a2 xQ + a4 ’ a1 yQ

x

Q

y

gQ = ’2yQ ’ a1 xQ ’ a3

x

(if 2Q = ∞)

gQ

vQ = y

x

2gQ ’ a1 gQ (if 2Q = ∞)

y

uQ = (gQ )2 .

Let C2 be the points of order 2 in C. Choose R ‚ C such that we have a

disjoint union

C = {∞} ∪ C2 ∪ R ∪ (’R)

(in other words, for each pair of non-2-torsion points P, ’P ∈ C, put exactly

one of them in R). Let S = R ∪ C2 . Set

v= vQ , w= (uQ + xQ vQ ).

Q∈S Q∈S

Then E2 has the equation

Y 2 + A1 XY + A3 Y = X 3 + A2 X 2 + A4 X + A6 ,

where

A1 = a1 , A2 = a2 , A3 = a3

A6 = a6 ’ (a2 + 4a2 )v ’ 7w.

A4 = a4 ’ 5v, 1

© 2008 by Taylor & Francis Group, LLC

´ 393

SECTION 12.3 VELU™S FORMULAS

The isogeny is given by

vQ uQ

X =x+ +

(x ’ xQ )2

x ’ xQ

Q∈S

xy

a1 uQ ’ gQ qQ

a1 (x ’ xQ ) + y ’ yQ

2y + a1 x + a3

Y =y’ uQ + vQ + .

(x ’ xQ )3 (x ’ xQ )2 (x ’ xQ )2

Q∈S

PROOF As in Section 8.1, let t = x/y and s = 1/y. Then t has a simple

zero and s has a third order zero at ∞ (see Example 11.3). Dividing the

relation y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 by y 3 and rearranging yields

s = t3 ’ a1 st + a2 st2 ’ a3 s2 + a4 s2 t + a6 s3 . (12.1)

If we substitute this value for s into the right hand side of (12.1), we obtain

s = t3 ’ a1 (t3 ’ a1 st + a2 st2 ’ a3 s2 + a4 s2 t + a6 s3 )t

+ a2 (t3 ’ a1 st + a2 st2 ’ a3 s2 + a4 s2 t + a6 s3 )t2 + · · · .

Continuing this process, we eventually obtain

1

= s = t3 1 ’ a1 t + (a2 + a2 )t2 ’ (a3 + 2a1 a2 + a3 )t3 + · · ·

1 1

y

and

y = t’3 + ±1 t’2 + ±2 t’1 + ±3 + ±4 t + ±5 t2 + ±6 t3 + O(t4 ),

where

±2 = ’a2 , ±4 = ’(a1 a3 + a4 ),

±1 = a1 , ±3 = a3 ,

±5 = a2 a3 + a2 a3 + a1 a4 ,

1

±6 = ’(a2 a4 + a3 a3 + a2 a4 + 2a1 a2 a3 + a2 + a6 ),

1 1 3

and where O(t4 ) denotes a function that vanishes to order at least 4 at ∞.

Since x = ty, we also obtain

x = t’2 + ±1 t’1 + ±2 + ±3 t + ±4 t2 + ±5 t3 + ±6 t4 + O(t5 ).

Substituting these expressions for x, y into the formulas given for X, Y yields

expressions for X, Y in terms of t. A calculation shows that

Y 2 + A1 XY + A3 Y = X 3 + A2 X 2 + A4 X + A6 + O(t),

where the Ai are as given in the statement of the theorem. Since X and Y

are rational functions of x, y, they are functions on E. The only poles of X

and Y are at the points in C, as can be seen from the explicit formulas for

© 2008 by Taylor & Francis Group, LLC

394 CHAPTER 12 ISOGENIES

X, Y . Therefore the function Y 2 + A1 XY + A3 Y ’ X 3 ’ A2 X 2 ’ A4 X ’ A6

can have poles only at the points of C. It vanishes at ∞, since it is O(t). We

want to show that it also vanishes at the nontrivial points of C. A calculation

(see Exercise 12.6) shows that

[x(P + Q) ’ x(Q)]

X(P ) = x(P ) + (12.2)

∞=Q∈C

[y(P + Q) ’ y(Q)] .

Y (P ) = y(P ) + (12.3)

∞=Q∈C

In particular, X and Y are invariant under translation by elements of C.

Therefore, Y 2 + A1 XY + A3 Y ’ X 3 ’ A2 X 2 ’ A4 X ’ A6 is invariant under

translation by elements of C. Since it vanishes at ∞, it vanishes at all points of

C. Hence it has no poles. This means that it is constant (see Proposition 11.1).

Since it vanishes at ∞, it is 0. This proves that X and Y satisfy the desired

generalized Weierstrass equation. The following shows that this equation gives

a nonsingular curve.

LEMMA 12.17

E2 is nonsingular.

PROOF For simplicity, assume that the characteristic of K is not 2. By

completing the square, we may reduce to the case where A1 = A3 = 0, so the

equation of E2 is

Y 2 = X 3 + A2 X 2 + A4 X + A6 = (X ’ e1 )(X ’ e2 )(X ’ e3 ).

We need to show that e1 , e2 , e3 are distinct. Suppose that e1 = e2 . Then

2

Y

X ’ e3 = .

X ’ e1

Let F = Y /(X ’ e1 ), which is a function on E.

The function X ’ e3 on E has double poles at the points of C and no other

poles. Therefore, its square root, namely F , has simple poles at the points of

C and no other poles. Note that F is invariant under translation by elements

of C, since both X and Y are. Let a ∈ K. Since F ’ a has N poles, where

N = #C, it has N zeros. If P is one of these zeros, then P + Q is also a zero

for each Q ∈ C. This gives all of the N zeros, so we conclude that F = a

occurs for exactly N distinct points of E.

We now need a special case of what is known as the Riemann-Hurwitz

formula. Consider an algebraic curve C de¬ned by a polynomial equation

G(x, y) = 0 over an algebraically closed ¬eld K. Let F (x, y) be a rational

function on C. Let n be the number of poles of F , counted with multiplicity.

If a ∈ K, then F ’a has n poles, hence n zeros. It can be shown that if F is not

© 2008 by Taylor & Francis Group, LLC

´ 395

SECTION 12.3 VELU™S FORMULAS

a pth power, where p is the characteristic of K, then for all but ¬nitely many

a, these n zeros are distinct (if F is a pth power, then F ’ a = (F 1/p ’ a1/p )p ,

so the roots cannot be distinct; that is why this case is excluded). We say

that n is the degree of F . If F ’ a has n distinct zeros for each a and F has

n distinct poles, then we say that F is unrami¬ed.

PROPOSITION 12.18 (Riemann-Hurwitz)

Let C1 , C2 be curves of genus g1 , g2 de¬ned over an algebraically closed ¬eld

K, and let F : C1 ’ C2 be an unrami¬ed rational map of degree n. Then

2g1 ’ 2 = n(2g2 ’ 2).

PROOF See [49]. More generally, the Riemann-Hurwitz formula can be

extended to cover the case where F is rami¬ed.

In our case, F is a function from the elliptic curve E, which has genus 1,

to the projective line P1 , which has genus 0. By the above discussion, F is

unrami¬ed of degree n. Therefore, 0 = ’2n, which is a contradiction.

We conclude that e1 , e2 , e3 must be distinct and therefore that E2 is non-

singular. This completes the proof of Lemma 12.17.

We have shown that ± : (x, y) ’ (X, Y ) gives a map from E to E2 . Equa-

tions (12.2), (12.3) show that the points in the subgroup C are exactly the

points mapping to ∞. In particular, since ∞ maps to ∞, Theorem 12.10

shows that ± is an isogeny. Its kernel is C. By Exercise 12.8, ± is separable.

This completes the proof of Theorem 12.16.

Example 12.4

Let E be given by y 2 = x3 + ax2 + bx, with b = 0 and a2 ’ 4b = 0 (these

conditions make the curve nonsingular). The point (0, 0) is a point of order 2,

so this point, along with ∞, gives a subgroup of order 2. The set S is {(0, 0)}.

y

x

For Q = (0, 0), we have vQ = gQ = a4 = b and gQ = 0, so uQ = 0. Therefore,

b by

Y =y’

X =x+ , .

x2

x

The curve E2 is given by the equation

Y 2 = X 3 + aX 2 ’ 4bX ’ 4ab.

Let

y2 x2 ’ b

ax + b by

Y3 = Y = y ’ 2 = y

X3 = X + a = x + = 2, .

x x x y

© 2008 by Taylor & Francis Group, LLC

396 CHAPTER 12 ISOGENIES

Then we obtain the elliptic curve E3 given by

Y32 = X3 ’ 2aX3 + (a2 ’ 4b)X3 .

3 2

The map ± : E ’ E3 is the same as the isogeny of Example 12.3.

The elliptic curve E3 has (0, 0) as a point of order 2. Repeating the proce-

dure for E3 yields an isogeny to the elliptic curve

E4 : Y42 = X4 + 4aX4 + 16bX4

3 2

with

’2aX3 + a2 ’ 4b (a2 ’ 4b)Y3

Y4 = Y3 ’

X 4 = X3 + , .

2 2

X3 X3

Let X5 = X4 /4, Y5 = Y4 /8. Then

Y52 = X5 + aX5 + bX5 ,

3 2

which is the equation of our original elliptic curve E. A calculation shows

that in the map E ’ E,

2

3x2 + 2ax + b

’ a ’ 2x,

x ’ X5 =

2y

which is exactly the formula for the x-coordinate of 2(x, y). A similar calcu-

lation for the y-coordinate tells us that the map E ’ E is multiplication by

2.

In summary, we have an isogeny ± : E ’ E3 and an isogeny ± : E3 ’ E

such that ± —¦ ± is multiplication by 2. The map ± is an example of a dual

isogeny.

12.4 Point Counting

In Section 4.5, we discussed the method of Schoof for counting the number

of points on an elliptic curve over a ¬nite ¬eld. In the present section, we

brie¬‚y sketch some work of Elkies and Atkin that uses isogenies to improve

the e¬ciency of Schoof™s algorithm.

Let E be an elliptic curve de¬ned over Fp . The p-power Frobenius endo-

morphism satis¬es φ2 ’aφ+p = 0 for some integer a, and #E(Fp ) = p+1’a.

Therefore, to count the number of points in E(Fp ), it su¬ces to ¬nd a.

Let = p be prime. Since the case = 2 can be treated as in Section 4.5,

assume is odd. The goal is to compute a (mod ). As in Schoof™s algorithm,

© 2008 by Taylor & Francis Group, LLC

397

SECTION 12.4 POINT COUNTING

if this is done for su¬ciently many , then we obtain a. As described in Section

4.5, the Frobenius acts on the -torsion E[ ] as a matrix

st

(φ) = .

uv

By Proposition 4.11, a ≡ Trace((φ) ) and p ≡ det((φ) ) (mod ). Suppose

there is a basis of E[ ] such that

»b

(φ) =

0µ

for some integers » and µ. This means that there is a subgroup C of E[ ]

such that φ(P ) = »P for all P ∈ C. Moreover,

T 2 ’ aT + p ≡ (T ’ »)(T ’ µ) (mod ).

Conversely, if T 2 ’ aT + p has a root » mod , then there is a subgroup C

such that φ(P ) = »P for all P ∈ C (this is the result from linear algebra that

the eigenvalues are the roots of the characteristic polynomial of a matrix).

Let C be a subgroup such that φq (P ) = »P for all P ∈ C, so the qth-power

Frobenius permutes the elements of C. Consider the isogeny with kernel C

constructed in Theorem 12.16. The formula for the isogenous curve E2 is

symmetric in the coordinates of the points of C. Since φq permutes these co-

ordinates, it leaves invariant the coe¬cients of equation of E2 . Consequently,

the j-invariant j2 of E2 is ¬xed by φq and therefore lies in Fq . Similarly, the

monic polynomial whose roots are the x-coordinates of the points in C has

coe¬cients that lie in Fq . There are ( ’ 1)/2 such coordinates, so we obtain a

polynomial F (x) of degree ( ’ 1)/2. Recall that the th division polynomial

ψ (x), whose roots are the x-coordinates of all the points in E[ ], has degree

( 2 ’ 1)/2. Therefore, F (x) is a factor of ψ (x) of degree much smaller than

ψ (x).

In Schoof™s algorithm, the most time-consuming parts are the computations

mod ψ (x). The ideas in Section 4.5 allow us to work mod F (x) instead, and

¬nd a » such that φ(P ) = »P for some P = ∞ in C. Since the degree of

F (x) is much smaller than the degree of ψ (x), the computations proceed

much faster. Since »µ ≡ p (mod ), we have

p

a ≡ Trace((φ) ) ≡ » + (mod ),

»

so we obtain a mod .

Finding F (x) e¬ciently is rather complicated. See [12] or [99] for details.

Determining whether » and µ exist is more straightforward and uses the

modular polynomial ¦ (X, Y ) (see Theorem 10.15). Recall that ¦ (X, Y ) has

integer coe¬cients. If j1 , j2 ∈ C, then ¦ (j1 , j2 ) = 0 if and only there is

an isogeny of degree from an elliptic curve with j-invariant j1 to one with

© 2008 by Taylor & Francis Group, LLC

398 CHAPTER 12 ISOGENIES

invariant j2 . It is easy to see from the construction of ¦ (x) that its degree is

+ 1, corresponding to the + 1 subgroups in E[ ] of order + 1. Since ¦ has

integer coe¬cients, we can regard it as a polynomial mod p. The following

analogue of Theorem 12.5 holds.

THEOREM 12.19

Let = p be prime, let j1 , j2 ∈ Fp , and let E1 , E2 be elliptic curves with

invariants j1 , j2 . Then ¦ (j1 , j2 ) = 0 if and only if there is an isogeny from

E1 to E2 of degree .

PROPOSITION 12.20

Let E be an elliptic curve de¬ned over Fp . Assume that E is not supersingular

and that its j-invariant j is not 0 or 1728. Let = p be prime.

1. Let j1 ∈ Fp be a root of the polynomial ¦ (j, T ), let E1 be an elliptic

curve of invariant j1 , and let C be the kernel of the corresponding isogeny

E ’ E1 of degree . Let r ≥ 1. There exists ν ∈ Z such that φr P = νP

for all P ∈ C if and only if j1 ∈ Fpr .

2. The polynomial ¦ (j, T ) factors into linear factors over Fpr if and only

if there exists ν ∈ Z such that φr P = νP for all P ∈ E[ ].

PROOF If φr P = νP for all P ∈ C, then, as discussed previously, the

j-invariant j1 of the isogenous curve is in Fpr . Similarly, if φr P = νP for all

P ∈ E[ ], then all -isogenous curves have j-invariants in Fpr , so all roots of

¦ (j, T ) are in Fpr .

For proofs of the converse statements, see [99].

REMARK 12.21 The restriction to j = 0, 1728 is necessary. See Exercise

12.11.

By computing gcd (T p ’ T, ¦ (j, T )) as a polynomial in F , we obtain a

polynomial whose roots are the roots of ¦ (j, T ) in F . Finding a root j1

of this polynomial allows us to construct a curve with j-invariant j1 (using

the formula on page 47) that is -isogenous to E. As mentioned previously,

a rather complicated procedure, described in [12] and [99], yields the desired

factor F (x) of the division polynomial ψ (x).

Example 12.5

Consider the elliptic curve E : y 2 = x3 √ x + 7 over F23 . The group E[3] is

+ √

generated by P1 = (1, 3) and P2 = (14, 5), where 5 ∈ F232 . Let φ be the

23rd power Frobenius endomorphism. Then φ(P1 ) = P1 and φ(P2 ) = ’P2 .

© 2008 by Taylor & Francis Group, LLC

399

SECTION 12.4 POINT COUNTING

Therefore, the subgroups C1 = {∞, P1 , ’P1 } and C2 = {∞, P2 , ’P2 } are such

that φ(P ) = »i P for all P ∈ Ci , where »1 = 1 and »2 = ’1.

The polynomials F (x) are x ’ 1 for C1 and x ’ 14 for C2 . They are factors

of the third division polynomial

ψ3 (x) ≡ 3x3 + 3x2 + 9x + 1 ≡ (x ’ 1)(3x + 4)(x2 + 15x + 6) (mod 23).

Either of »1 , »2 can be used to obtain a mod 3:

23

a ≡ »i + ≡0 (mod 3).

»i

Therefore, #E(F23 ) = 23 + 1 ’ a ≡ 0 (mod 3). Since x3 + x + 7 has

x = ’3 as a root mod 23, E(F23 ) contains a point of order 2. Therefore,

#E(F23 ) ≡ 0 (mod 6). The Hasse bounds tell us that 15 ¤ #E(F23 ) ¤ 33,

hence #E(F23 ) = 18, 24, or 30. In fact, counting points explicitly shows that

the group has order 18.

Let Ei be the image of the isogeny with kernel Ci . The j-invariant of E is

18. The modular polynomial ¦3 (18, T ) factors as

¦3 (18, T ) ≡ (T + 1)(T + 3)(T 2 + 2T + 10) (mod 23)

(the polynomial ¦3 is given on page 329). Therefore, there are two 3-isogenous

curves whose j-invariants are in F23 . They have j = ’1 and j = ’3. One of

these is E1 and the other is E2 . Which is which? (Exercise 12.14).

The following result, due to Atkin, shows that the possible factorizations of

¦ (j, T ) mod are rather limited.

THEOREM 12.22

Let E be an elliptic curve de¬ned over Fp . Assume that E is not supersingular

and that its j-invariant j is not 0 or 1728. Let = p be prime. Let

¦ (j, T ) ≡ f1 (T ) · · · fs (T ) (mod )

be the factorization of ¦ (j, T ) into irreducible polynomials mod . The degrees

of the factors are one of the following:

1. 1 and (and s = 2)

2. 1, 1, r, r, . . . , r (and s = 2 + ( ’ 1)/r)

3. r, r, . . . , r (and s = ( + 1)/r).

In (1), a2 ’ 4p ≡ 0 (mod ). In (2), a2 ’ 4p is a square mod . In (3), a2 ’ 4p

is not a square mod . In cases (2) and (3),

a2 ≡ (ζ + 2 + ζ ’1 )p for some primitive rth root of unity ζ ∈ F .

(mod )

© 2008 by Taylor & Francis Group, LLC

400 CHAPTER 12 ISOGENIES

PROOF The matrix (φ) has characteristic polynomial F (T ) = T 2 ’aT +p.

If F (T ) factors into distinct linear factors (T ’ »)(T ’ µ) mod , then we

can ¬nd a basis of E[ ] that diagonalizes (φ) . An eigenvector for » is a

point P that generates a subgroup C1 such that φ(P ) = »P for all P ∈ C1 .

The eigenvalue µ yields a similar subgroup C2 . Since » and µ are the only

two eigenvalues, C1 and C2 are the only two subgroups on which φ acts by

multiplication by an integer. By Proposition 12.20, there are exactly two

corresponding j-invariants in Fp that are roots of ¦ (j, T ). Let j3 = j1 , j2 be

another root of ¦ (j, T ), and let r be the smallest integer such that j3 ∈ Fpr .

By part (1) of Proposition 12.20, there is a subgroup C3 of E[ ] and an integer

ν such that φr (P ) = νP for all P ∈ C3 . Moreover, C3 is the kernel of the

isogeny to a curve of invariant j3 = j1 , j2 , hence C3 = C1 , C2 . This means

that C1 , C2 , C3 are distinct eigenspaces of the 2 — 2 matrix (φ)r , so (φ)r must

be scalar. Consequently, all subgroups C of order are eigenspaces of (φ)r .

Part (1) of Proposition 12.20 implies that all roots of ¦ (j, T ) lie in Fpr . We

have therefore proved that all roots lie in the same ¬eld as j3 . Since j3 was

arbitrary, r is equal for all roots j3 = j1 , j2 . Since the minimal r such that

j3 ∈ Fpr is the degree of the irreducible factor that has j3 as a root, all

irreducible factors of ¦ (j, T ), other than T ’ j1 and T ’ j2 , have degree r.

This is Case (2). Since T 2 ’ aT + p factors in F , its discriminant a2 ’ 4p is

a square (this follows from the quadratic formula).

If F (T ) = (T ’ »)2 for some µ, then either (φ) is the scalar matrix »I, or

there is a basis for E[ ] such that

»1

(φ) = .

0»

(This is the nondiagonal case of Jordan canonical form.) In the ¬rst case,

part (2) of Proposition 12.20 implies that ¦ (j, T ) factors into linear factors

in Fp , and a2 ’ 4p ≡ 0 (mod ), which is a square. This is the case r = 1 in

Case (2). In the other case, an easy induction shows that

k

»k k»k’1

»1

= .

0 »k

0»

This is nondiagonal when k < and diagonal when k = . Therefore, the

smallest r such that (φ)r has two independent eigenvectors is r = , and (φ) is

scalar. The reasoning used in Case (2) shows that ¦ (j, T ) has an irreducible

factor of degree . This yields Case (1). Since F (T ) has a repeated root,

a2 ’ 4p ≡ 0 (mod ).

Finally, suppose F (T ) is irreducible over F . Then a2 ’ 4p is not a square

mod . There are no nontrivial eigenspaces over F , so there are no linear

factors of ¦ (j, T ) over F . Let » and µ be the two roots of F (T ). They lie

in F 2 and are quadratic conjugates of each other. The eigenvalues of (φ)k

are »k and µk . Let k be the smallest exponent so that »k ∈ F . This is the

smallest k such that (φ)k has an eigenvalue in Fp , and therefore Fpk is the

© 2008 by Taylor & Francis Group, LLC

401

SECTION 12.5 COMPLEMENTS

smallest ¬eld containing a root of ¦ (j, T ), by Proposition 12.20. Since »k

and µk are quadratic conjugates and lie in F , they are equal. Therefore, (φ)k

is scalar, so all roots of ¦ (j, T ) lie in Fpk , but none lies in any smaller ¬eld.

It follows that all the irreducible factors of ¦ (j, T ) have degree r = k. This

is Case (3).

In all three cases, the eigenvalues (or diagonal elements in Case (1)) of

(φ) are » and µ = p/». We have a = Trace((φ) ) = » + µ. Moreover,

»r = µr = pr /»r since (φ)r is scalar. Therefore, »2r = pr , hence »2 = pζ for

an rth root of unity ζ. This implies that

p2

p2

2

= » + 2p + 2 = p ζ + 2 + ζ ’1 .

2

a = »+

» »

Suppose we are in Case (2) or (3). If ζ k = 1 for some k < r, then »2k = pk =

»k µk , so »k = µk . This means that (φ)k is scalar, which contradicts the fact

that r is the smallest k with this property. Therefore, ζ is a primitive rth root

of unity. (Note that in Case (1), we have ζ = 1 and there are no primitive th

roots of unity in F .) This completes the proof of the theorem.

In Example 12.5, the factorization of ¦3 had factors of degrees 1, 1, 2, which

is case (2) of the theorem with r = 2.

The primes corresponding to Cases (1) and (2) are called Elkies primes.

Those for Case (3) are called Atkin primes. Atkin primes put restrictions

on the value of a mod , but they allow many more possibilities than the

Elkies primes, which, after some more work, allow a determination of a mod

. However, Atkin showed how to combine information obtained from the

Atkin primes with the information obtained from Elkies primes to produce an

e¬cient algorithm for computing a mod (see [12, Section VII.9]).

12.5 Complements

Isogenies occur throughout the theory of elliptic curves. In Section 8.6,

Fermat™s in¬nite descent involved two elliptic curves that are 2-isogenous. In

fact, the descent procedure of Section 8.2 can sometimes be re¬ned using an

isogeny and its dual isogeny. This is what is happening in Section 8.6. See

[109] for the general situation.

Let E1 , E2 be elliptic curves over Fq . If they are isogenous over Fq , then

#E1 (Fq ) = #E2 (Fq ) (Exercise 12.12). The amazing fact that the converse is

true was proved by Tate. In other words, if #E1 (Fq ) = #E2 (Fq ) then E1 , E2

are isogenous over Fq . The condition #E1 (Fq ) = #E2 (Fq ) can be interpreted

as saying that E1 and E2 have the same zeta function (see Section 14.1), so

we see that the zeta function uniquely determines the isogeny class over Fq

of an elliptic curve.

© 2008 by Taylor & Francis Group, LLC

402 CHAPTER 12 ISOGENIES

A similar situation holds over Q, as was proved by Faltings in 1983. Namely,

if E1 , E2 are elliptic curves over Q, then the L-series of E1 (see Section 14.2)

equals the L-series of E2 if and only if E1 and E2 are isogenous over Q. This

theorem arose in his proof of Mordell™s conjecture that an algebraic curve of

genus at least 2 has only ¬nitely many rational points.

Exercises

12.1 Let L be the lattice Z + Zi.

(a) Show that [1 + i] : C/L ’ C/L is an isogeny. List the elements of

the kernel and conclude that the isogeny has degree 2.

(b) Let 0 = a + bi ∈ Z + Zi. Show that [a + bi] : C/L ’ C/L is an

isogeny of degree a2 + b2 . (Hint: The proof of Lemma 12.1 shows

that the degree is the determinant of a + bi acting on the basis

{1, i} of L.)

12.2 Let E = C/L be an elliptic curve de¬ned over C. Let n be a positive

integer. Let [±] : C/L ’ C/L1 be an isogeny and assume that E[n] ⊆

Ker ±. By multiplying by ±’1 , we may assume that the isogeny is given

by the map z ’ z and that L ⊆ L1 , so L1 /L is the kernel of the isogeny.

For convenience, we continue to denote the isogeny by [±].

1

n L/L.

(a) Show that E[n] =

1

(b) Let ±1 : C/L ’ the map given by z ’ z. Show that

C/ n L be

1

there is an isomorphism β : C/ n L C/L such that β —¦ ±1 = [n]

(= multiplication by n on E).

(c) Observe that ± factors as ±2 —¦ ±1 , where ±1 is as in (b), and where

1

±2 : C/ n L ’ C/L1 is given by z ’ z. Let ±3 = ±2 —¦ β ’1 .

Conclude that ± factors as ±3 —¦ [n].

(d) Let γ : E ’ E1 be an isogeny with Ker γ Zn1 • Zn2 with n1 |n2 .

Show that γ equals multiplication by n1 on E composed with a

cyclic isogeny whose kernel has order n2 /n1 .

12.3 Let [±] : C/L1 ’ C/L2 be an isogeny, as in Section 12.1.

(a) Show that deg([±]) = deg([±]) (Hint: multiplication by N/± cor-

responds to the matrix N (aij )’1 , in the notation of the proof of

Lemma 12.1).

(b) Show that [±] = [±].

© 2008 by Taylor & Francis Group, LLC

403

EXERCISES

12.4 Let E1 : y1 = x3 + ax2 + bx1 be an elliptic curve over some ¬eld of

2

1 1

characteristic not 2 with b = 0 and a2 ’ 4b = 0. Let E2 be the elliptic

curve y2 = x3 ’ 2ax2 + (a2 ’ 4b)x2 . De¬ne ± by

2

2 2

y1 y1 (x2 ’ b)

2

1

(x2 , y2 ) = ±(x1 , y1 ) = 2, .

x2

x1 1

Let si = 1/yi and ti = xi /yi . Then ti and si are 0 at ∞ (in fact, ti has a

simple zero at ∞ and si has a triple zero at ∞, but we won™t use this).

We want to show that ±(∞) = ∞. To do this, whenever we encounter

an expression 0/0 or ∞/∞, we rewrite it so as to obtain an expression

in which every part is de¬ned.

(a) Show that

s1 s1 1

s2 = , t2 = 2 1 ’ b(s /t )2 .

1 ’ b(s1 /t1 )2 t1 11

(b) Show that s1 /t1 = t2 + as1 t1 + bs2 , so s1 /t1 is 0 at ∞.

1 1

(c) Write

2

s1 s1

= t1 + as1 + b t1 .

t2 t1

1

Show that s1 /t2 has the value 0 at ∞.

1

(d) Show that ± maps ∞ on E1 to ∞ on E2 .

12.5 Let E1 , E2 , ±, s2 , t2 be as in Exercise 12.4.

(a) Show that

x1 y1 y1

s2 = , t2 = .

(x2 + ax1 + b)(x2 ’ b) x2’b

1 1 1

(b) Conclude that ±(0, 0) = ∞.

12.6 Let E be an elliptic curve given by a generalized Weierstrass equation

y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 . Let P = (xP , yP ) and Q =

(xQ , yQ ) be points on E. Let xP +Q , yP +Q denote the x and y coordinates

of the point P + Q.

(a) Show that if 2Q = ∞, then uQ = 0 and

a1 (xP ’ xQ ) + yP ’ yQ

vQ

xP +Q ’xQ = yP +Q ’yQ = ’

, vQ .

(xP ’ xQ )2

xP ’ xQ

© 2008 by Taylor & Francis Group, LLC

404 CHAPTER 12 ISOGENIES

(b) Show that if 2Q = ∞, then

vQ uQ

xP +Q ’ xQ + xP ’Q ’ x’Q = + ,

(xP ’ xQ )2 (xP ’ xQ )3

yP +Q ’ yQ + yP ’Q ’ y’Q

a1 (xP ’ xQ ) + yP ’ yQ

2yP + a1 xP + a3

= ’uQ ’ vQ

(xP ’ xQ )3 (xP ’ xQ )2

xy

a1 uQ ’ gQ gQ

’ .

(xP ’ xQ )2

(c) Show that, in the notation of Theorem 12.16,

[x(P + Q) ’ x(Q)]

X(P ) = x(P ) +

∞=Q∈C

[y(P + Q) ’ y(Q)] .

Y (P ) = y(P ) +

∞=Q∈C

12.7 Let p(T ), q(T ) be polynomials with coe¬cients in a ¬eld K with no

common factor. Let X be another variable. Show that the polynomial

F (T ) = p(T ) ’ Xq(T ), regarded as a polynomial with coe¬cients in

K(X), is irreducible. (Hint: By Gauss™s Lemma (see, for example,

[71]), if F (T ) factors, it factors with coe¬cients that are polynomials

in X (that is, we do not need to consider polynomials with rational

functions as coe¬cients).)

12.8 Recall that in V´lu™s formulas,

e

vQ uQ

+ .

X =x+

(x ’ xQ )2

x ’ xQ

Q∈S

y

(a) Show that gQ = 0 if and only if 2Q = ∞. Show that if 2Q = ∞,

x

then gQ = 0 (Hint: the curve is nonsingular). Conclude that if

2Q = ∞ then vQ = 0, and that uQ = 0 if and only if 2Q = ∞.

(b) Write the rational function de¬ning X as p(x)/q(x), where p, q are