Cryptography Reference
In-Depth Information
S
S
vertices are the
O
-ideal classes in the coset a
and such that, for each b
∈
a
and each
S
, there is an edge between b and l
−
i
b. Since ideal class groups are well-understood,
this correspondence illuminates the study of the isogeny graph. For example, an immediate
corollary is that the graph of elliptic curves
E
with End(
E
)
l
i
∈
=
O
is connected if and only
if
S
generates Cl(
). A well-known result of Bach states that (assuming the Riemann
hypothesis for the Dedekind zeta function of
K
and Hecke
L
-functions for characters of
Cl(
O
)
2
(see
O
K
)) the group Cl(
O
K
) is generated by prime ideals of norm less than 6 log(
|
K
|
page 376 of [
19
]) where
K
is the discriminant of
O
K
. Another immediate corollary is that
the graph is regular (i.e., every vertex has the same degree).
Remark 25.3.6
We stress that there is no canonical choice of
O
-ideal a corresponding to
. However, given a pair (
E,E
) of isogenous elliptic
an elliptic curve
E
with End(
E
)
=
O
End(
E
)
curves with End(
E
)
the ideal class corresponding to the isogeny between
them is well-defined. More precisely, if
E
is identified with
=
=
O
C
/
a for some
O
-ideal a then
there is a unique ideal class represented by b such that
E
is identified with
/
b
−
1
a.The
only algorithm known to find such an ideal b is to compute an explicit isogeny from
E
to
E
(using algorithms presented later in this chapter) and then determine the corresponding
isogeny. If one could determine b efficiently from
E
and
E
then navigating the ordinary
isogeny graph would be much easier.
C
Exercise 25.3.7
Let
E
1
be an elliptic curve with End(
E
1
)
=
O
.Letl be a prime ideal of
O
above
. Suppose l has order
d
in Cl(
O
). Show that there is a cycle
E
1
→
E
2
→···→
E
d
→
E
1
of
-isogenies.
F
q
and let
E
be the quadratic
twist of
E
. Show that the graphs
X
E,
F
q
,S
and
X
E
,
F
q
,S
are identical.
Exercise 25.3.8
Let
E
be an ordinary elliptic curve over
Remark 25.3.9
Let
split in
O
= Z
[
θ
]
⊆
End(
E
) and let l
1
=
(
,a
+
θ
) and l
2
=
(
,b
+
→
E
of degree
one can
determine whether
φ
corresponds to l
1
or l
2
as follows: compute (using the Elkies method
if only
j
(
E
) and
j
(
E
) are known) the polynomial determining the kernel of
φ
; compute an
explicit point
P
θ
) be the corresponding prime ideals. Given an isogeny
φ
:
E
=
O
E
.This
trick is essentially due to Couveignes, Dewaghe, and Morain (see Section 3.2 of [
144
]; also
see pages 49-50 of Kohel [
315
] and Galbraith, Hess and Smart [
204
]).
∈
ker(
φ
); check whether [
a
]
P
+
θ
(
P
)
=
O
E
or [
b
]
P
+
θ
(
P
)
F
q
with the
Remark 25.3.10
The ideas mentioned above show that all elliptic curves over
same endomorphism ring are isogenous over
F
q
. Combined with the results of Section
25.4
one can prove Tate's isogeny theorem, namely that any two elliptic curves over
F
q
with the
same number of points are isogenous over
F
q
.
More details about the structure of the ordinary isogeny graph will be given in Sec-
tion
25.4
. In particular, that section will discuss isogenies between elliptic curves whose
endomorphism rings are different orders in the same quadratic field.
