Cryptography Reference
In-Depth Information
O
K
42
O
2
14
33
57
O
3
51
35
O
6
44
4
18
32
Figure 25.2 A 2-isogeny graph with two volcanoes. The symbols on the left hand side denote the
endomorphism ring of curves on that level, using the same notation as Example
25.4.4
.
[
π
q
]. Consider the subgraph of the isogeny
graph corresponding to isogenies whose degree is equal to
. We call this the
-isogeny
graph. This graph is often not connected (for example, it is not connected when
c
is not
a power of
or when primes above
do not generate Cl(
Fix a prime
|
c
where
c
is the conductor of
Z
O
K
)). Even when
splits and
c
is 1 or a power of
, the graph is often not connected (the graph is connected only when
the prime ideals above
generate the ideal class group). Theorem
25.4.6
shows that each
component of the
-isogeny graph has a particular shape (that Fouquet and Morain [
192
]
called a
volcano
).
We now give a precise definition for volcanoes. Let #
E
(
F
q
)
=
q
+
1
−
t
and let
c
be
(
t
2
O
K
the
maximal order in
K
.A
volcano
is a connected component of the graph
X
E,
F
q
,
{
}
. A volcano
has
m
Z
[
π
q
] and suppose
m
= Q
−
the conductor of
c
.Let
K
4
q
) and denote by
1 “levels”
V
0
,...,V
m
, being subgraphs of the
-isogeny graph; where vertices
in
V
i
(i.e., on level
i
) correspond to isomorphism classes of elliptic curves
E
such that
i
+
O
K
:End(
E
)]. In other words,
V
0
is on the surface of this component of the
-isogeny
graph (but not necessarily on the surface of the entire isogeny graph
X
E,
F
q
,S
) and
V
m
is on the
floor of this component of the
-isogeny graph (though, again, not necessarily on the floor
of the whole isogeny graph). The surface of a volcano (i.e.,
V
0
) is also called the
crater
.The
graph
V
0
is a connected regular graph with each vertex of degree at most 2. For all 0
<i
[
≤
m
and every vertex
v
∈
V
i
there is a unique edge from
v
“up” to a vertex in
V
i
−
1
. For all
0
≤
i<m
and every
v
∈
V
i
the degree of
v
is
+
1. Every vertex in
V
m
has degree 1.
25.4.2 Kohel's algorithm (ordinary case)
Kohel used the results of Section
25.4.1
to develop deterministic algorithms for computing
End(
E
) (i.e., determining the level) for an elliptic curve
E
over
F
q
. We sketch the algorithm
