Cryptography Reference
In-Depth Information
25.4.1 Isogeny volcanoes
Let
E
be an ordin
ary ellip
tic curve over
F
q
and let #
E
(
F
q
)
=
q
+
1
−
t
. Denote by
K
the
(
t
2
number field
Q
−
4
q
) and by
O
K
the ring of integers of
K
. We k
now tha
t End(
E
)
=
t
2
End
F
q
(
E
) is an order in
O
K
that contains the order
Z
[
π
q
]
= Z
[(
t
+
−
4
q
)
/
2] of dis-
criminant
t
2
4
q
)
/c
2
where
c
is the largest positive integer such that
K
is an integer congruent to 0 or 1 modulo 4. The
integer
c
is the
conductor
of the order
(
t
2
−
4
q
.Let
K
be the discriminant of
K
, namely
K
=
−
[
π
q
].
Suppose
E
1
and
E
2
are elliptic curves over
Z
F
q
such that End(
E
i
)
=
O
i
,for
i
=
1
,
2,
where
O
1
and
O
2
are orders in
K
containing
Z
[
π
q
]. We now present some results about
the isogenies between such elliptic curves.
→
E be an isogeny of elliptic curves over
Lemma 25.4.1
Let φ
:
E
F
q
.If
[End(
E
):
End(
E
)]
=
(or vice versa) then the degree of φ is divisible by .
Proof
See Propositions 21 and 22 of Kohel [
315
].
Definition 25.4.2
Let
be a prime and
E
an elliptic curve. Let End(
E
)
=
O
.An
-isogeny
→
E
is called
horizontal
(respectively,
ascending
,
descending
)ifEnd(
E
)
=
O
(respectively, [End(
E
):
φ
:
E
:End(
E
)]
O
]
=
,[
O
=
).
→
E
be an
-isogeny. Show that if
φ
is horizontal (respectively,
ascending, descending) then
φ
is horizontal (respectively, descending, ascending).
Exercise 25.4.3
Let
φ
:
E
Example 25.4.4
We now give a picture of how the orders relate to one another. Suppose
the conductor of
Z
[
π
q
]is6(e.g.,
q
=
31 and
t
=±
4) so that [
O
K
:
Z
[
π
q
]]
=
6. Write
O
K
= Z
[
θ
]. Then the orders
O
2
= Z
[2
θ
] and
O
3
= Z
[3
θ
] are contained in
O
K
and are
such that [
O
K
:
O
i
]
=
i
for
i
=
2
,
3.
O
K
3
2
O
3
O
2
3
2
Z
[
π
q
]
=
O
K
then
E
is said to be on
Definition 25.4.5
Let the notation be as above. If End(
E
)
the
surface
of the isogeny graph.
11
If End(
E
)
= Z
[
π
q
] then
E
is said to be on the
floor
of
the isogeny graph.
By the theory of complex multiplication, the number of isomorphism classes of elliptic
curves over
F
q
on the surface is equal to the ideal class number of the ring
O
K
.
11
Kohel's metaphor was intended to be aquatic: the floor represents the ocean floor and the surface represents the surface of the
ocean.
