Isogenies - Elliptic Curves: Number Theory and Cryptography - page 383

PROOF Write j k = j ( τ k )forsome τ k . Suppose Φ N ( j 1 ,j 2 )=0. Then

j ( τ 1 )= j ( S ( τ 2 )) for some S = ab

∈ S N . By Corollary 9.19, there

0 d

exists M = st

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

uv

τ 1 = ω 1 /ω 2 for some basis {ω 1 ,ω 2 } of L 1 , 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 L 1 since M ∈ SL 2 ( Z ).
We conclude that there exist bases

ω ( i ) ,ω ( i )

{ } of L i ,for i =1 , 2, such that

1 2

ω (1)

= S ( τ 2 )= aω (2)

+ bω (2)

1
ω (1)

1 2

.

dω (2)

2 2

Let α =( aω (2)

2 . Therefore αω (1 i ,for
i =1 , 2, is a linear combination with integer coe cients of the basis elements
of L 2 ,so αL 1 ⊆

+ bω (2) ) /ω (1) .Then αω (1) = dω (2)

1 2 1 2

L 2 . As we saw in the proof of Lemma 12.1, the index

[ L 2 : αL 1 ] is the determinant of ab

,whichis N . Therefore, [ α ]givesan

0 d

N -isogeny from C /L 1 to C /L 2 .
Conversely, suppose that there is an N -isogeny [ α ]from C /L 1 to C /L 2 .
Write

α ω (1)

=( a ij ) ω (2) ,

1
ω (1)

1
ω (2)

2 2

as in Lemma 12.1. By Lemma 10.10, we can write
a 11 a 12
a 21 a 22

= b 11 b 12 ab

0 d b 21 b 22

with ( b ij ) ∈ SL 2 ( Z ). Let

=( b ij ) − 1 ω (1)

.

ω 1
ω 2

1
ω (1)

2

Then

ω (2)

.

α ω 1

= ab

1
ω (2)

ω 2

0 d

2

Therefore,

= aω (2)

+ bω (2)

ω 1
ω 2

= aτ 2 + b
d

1 2

,

dω (2)

2

where τ 2 = ω (2) /ω (2)

ω 1 ,ω 2 } . The fact that ( b ij ) ∈ SL 2 ( Z ) implies that { is a

1 2

basis of L 1 .Since j 1 = j ( ω 1 /ω 2 ), we obtain
j 1 = j ( S ( τ 2 )) , where S = ab

.

0 d