. 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, [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
(φ) =


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
(φ) = .


(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


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

. 1
( 2)



>>