Cryptography Reference
In-Depth Information
Theorem 25.4.6
Let E be an ordinary elliptic curve over
F
q
as above and let
O
=
End(
E
)
be an order in
O
K
containing
Z
[
π
q
]
. Let c
=
[
O
K
:
O
]
and let be a prime. Every-isogeny
→
E arises from one of the following cases.
φ
:
E
(
t
2
−
4
q
If
c then there are exactly
(1
+
))
equivalence classes of horizontal -isogenies
F
q
from E to other elliptic curves.
12
over
If
|
c then there are no horizontal -isogenies starting at E.
If
|
c there is exactly one ascending -isogeny starting at E.
If
|
[
O
:
Z
[
π
q
]]
then the number of equivalence classes of -isogenies starting fromE is
1
, where the horizontal and ascending isogenies are as described and the remaining
isogenies are descending.
+
If
[
O
:
Z
[
π
q
]]
then there is no desending -isogeny.
Proof
See Proposition 23 of Kohel [
315
]. A proof over
C
is also given in Appendix A.5
of [
200
].
Corollary 25.4.7
Let E be a
n ordina
ry elliptic curve over
F
q
with
#
E
(
F
q
)
=
q
+
1
−
t.
[
t
2
Let c be the conductor of
Z
−
4
q
]
and suppose
|
c. Then
[End(
E
):
Z
[
π
q
]]
if and
only if there is a single -isogeny over
F
q
starting from E.
67 and consider the elliptic curve
E
:
y
2
x
3
Example 25.4.8
Let
q
=
=
+
11
x
+
21 over
4 and
t
2
2
2
3
2
F
q
. One has #
E
(
F
q
)
=
64
=
q
+
1
−
t
where
t
=
−
4
q
=
·
·
(
−
7). Further,
+
√
−
j
(
E
)
=
42
≡−
3375 (mod 67)
, so
E
has complex multiplication by (1
7)
/
2. Since
(
√
−
the ideal class number of
7) is 1, it follows that
E
is the unique elliptic curve up to
isomorphism on the surface
of th
e isogeny graph.
Since 2 splits in
Q
+
√
−
7)
/
2] there are two 2-isogenies from
E
to elliptic curves on
the surface (i.e., to
E
itself) and so there is only one 2-isogeny down from
E
.Usingthe
modular polynomial we deduce that the 2-isogeny down maps to the isomorphism class of
elliptic curves with
j
-invariant 14. One can verify that the only 2-isogeny over
Z
[(1
F
q
from
j
=
14 is the ascending isogeny back to
j
=
42.
We have (
−
3
1 so there are no horizontal 3-isogenies from
E
. Hence, we expect four
3-isogenies down from
E
. Using the modular polynomial we compute the corresponding
j
-invariants to be 33
,
35
,
51 and 57. One can now consider the 2-isogeny graphs containing
these elliptic curves on their surfaces. It turns out that the graph is connected, and that
there is a cycle of horizontal 2-isogenies from
j
)
=−
57. For
each vertex we therefore only expect one 2-isogeny down to the floor. The corresponding
j
-invariants are 44
,
4
,
18 and 32 respectively. Figure
25.2
gives the 2-isogeny graph in this
case.
=
33 to
j
=
51 to
j
=
35 to
j
=
Exercise 25.4.9
Draw the 3-isogeny graph for the elliptic curves in Example
25.4.8
.Is
X
E,
F
q
,
{
2
,
3
}
connected? If so, what is its diameter?
The symbol (
t
2
−
4
q
) is the Kronecker symbol as in equation (
25.4
).
12
