Cryptography Reference
In-Depth Information
T
heorem 25.3.17
Let p be a prime and let E and E be supersingular elliptic c
urv
es over
F
p
. Let be a prime different from p. Then there is an isogeny from E to E over
F
p
whose
degree is a power of .
Proof
See Corollary 78 of Kohel [
315
] or Section 2.4 of Mestre [
377
].
Hence, one can choose any prime
(e.g.,
=
2) and consider the
-isogeny graph
X
E,
F
p
,
{
}
on supersingular curves over
F
p
. It follows that the graph is (
+
1)-regular and
connected.
Exercise 25.3.18
Let
p
103. Determine, using Theorem
9.11.11
, the number of iso-
morphism classes of supersingular elliptic curves over
=
F
p
and over
F
p
2
. Determine the
F
p
2
.
2-isogeny graph whose vertices are supersingular elliptic curves over
Exercise 25.3.19
Determine the supersingular 2-isogeny graph over
F
11
. Interpret the
results in light of Remark
25.3.2
.
10
[Hint: The isomorphism classes of elliptic curves with
j
(
E
)
1728 are
supersingular modulo 11; this follows from the theory of complex multiplication and the
facts that (
−
3
=
0 and
j
(
E
)
=
(
−
4
11
)
=
11
)
=−
1.]
Exercise 25.3.20
Find a prime
p
such that the set of isomorphism classes of supersingular
elliptic curves over
F
p
does not form a connected subgraph of
X
E,
F
p
,
{
2
}
.
F
p
and projective right modules of rank 1 of a maximal order of the quaternion algebra over
Q
There is a one-to-one correspondence between supersingular elliptic curves
E
over
(see Section 5.3 of Kohel [
315
]orGross[
244
]). Pizer has exploited
this structure (and connections with Brandt matrices and Hecke operators) to show that the
supersingular isogeny graph is a Ramanujan graph. Essentially, the Brandt matrix gives the
adjacency matrix of the graph. A good survey is [
431
], though be warned that the paper
does not mention the connection to supersingular elliptic curves.
The supersingular isogeny graph has been used by Charles, Goren and Lauter [
120
]to
construct a cryptographic hash function. It has also been used by Mestre and Oesterl´e[
377
]
for an algorithm to compute coefficients of modular forms.
ramified at
p
and
∞
25.4 The structure of the ordinary isogeny graph
This section presents Kohel's results on the structure of the isogeny graph of ordinary
elliptic curves over finite fields. Section
25.4.2
gives Kohel's algorithm to compute End(
E
)
for a given ordinary elliptic curve over a finite field.
10
This example was shown to me by David Kohel.
