ÒÚ. 1(‚ÒÂ„Ó 2)—Œƒ≈–∆¿Õ»≈ >>
Chapter 12
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, ). 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 .
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 .

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 .
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 . 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  or  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 .

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  and , 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 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
 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,
), 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
 ÒÚ. 1(‚ÒÂ„Ó 2)—Œƒ≈–∆¿Õ»≈ >>