Cryptography Reference
In-Depth Information
edge (
j
(
E
1
)
,j
(
E
2
)) labelled by
for each equivalence class of
-isogenies from
E
1
to
E
2
defined over
k
for some
∈
S
. We usually treat this as an undirected graph, since for
E
2
there is a dual isogeny
φ
:
E
2
→
every
-isogeny
φ
:
E
1
→
E
1
of degree
(though see
Remark
25.3.2
for an unfortunate, though rare, complication).
Remark 25.3.2
Edges in the isogeny graph correspond to equivalence classes of isogenies.
It can happen that two non-equivalent isogenies from
E
1
→
E
2
have equivalent dual
isogenies from
E
2
→
E
1
. It follows that there are two directed edges in the graph from
E
1
to
E
2
but only one directed edge from
E
2
to
E
1
. (Note that this does not contradict the fact
that isogenies satisfy
φ
φ
, as we are speaking here about isogenies up to equivalence.)
Such an issue was already explained in Exercise
25.1.1
; it only arises if #Aut(
E
2
)
>
2 (i.e.,
if
j
(
E
2
)
=
=
0
,
1728).
Definition 25.3.3
A (directed) graph is
k
-regular
if every vertex has (out-)degree
k
(a
loop is considered as having degree 1). A
path
in a graph is a sequence of (directed) edges
between vertices, such that the end vertex of one edge is the start vertex of the next. We will
also describe a path as a sequence of vertices. A graph is connected if there is a path from
every vertex to every other vertex. The
diameter
of a connected graph is the maximum,
over all pairs
v
1
,v
2
of vertices in the graph, of the length of the shortest path from
v
1
to
v
2
.
There are significant differences (both in the structure of the isogeny graph and the way
it is used in applications) between the ordinary and supersingular cases. So we present them
separately.
25.3.1 Ordinary isogeny graph
Fix an ordinary elliptic curve
E
over
F
q
such that #
E
(
F
q
)
=
q
+
1
−
t
. The isogeny graph
of elliptic curves isogenous over
F
q
to
E
can be identified, using the theory of complex
multiplication, with a graph whose vertices are ideal classes (in certain orders). The goal
of this section is to briefly sketch this theory in the special case (the general case is given in
Section
25.4
) of the subgraph where all elliptic curves have the same endomorphism ring,
in which case the edges correspond to multiplication by prime ideals. We do not have space
to give all the details; good references f
or
the background are Cox [
145
] and Lang [
328
].
The en
domorph
ism ring of
E
(over
F
q
) is an order
O
in the quadratic imaginary field
(
t
2
K
= Q
−
4
q
). (We refer to Section
A.12
for backgroun
d on ord
ers and conductors.)
+
t
2
Let
O
K
be the ring of integers of
K
. Then
Z
[
π
q
]
= Z
[(
t
−
4
q
)
/
2]
⊆
O
⊆
O
K
and
if
O
K
= Z
[
θ
] then
O
= Z
[
cθ
] where
c
is the conductor of
O
. The ideal class group Cl(
O
)
is defined to be the classes of invertible
-ideals that are prime to the conductor; see
Section 7 of [
145
] or Section 8.1 of [
328
]. There is an explicit formula for the order
h
(
O
O
)
of the ideal class group Cl(
O
) in terms of the class number
h
(
O
K
) of the number field; see
Theorem 7.24 of [
145
] or Theorem 8.7 of [
328
].
There is a one-to-one correspondence between the set of isomorphism classes of elliptic
curves
E
over
F
q
with End(
E
)
=
O
and the set Cl(
O
). Precisely, to an invertible
O
-ideal
