Cryptography Reference
In-Depth Information
-ideal a
is equivalent to a in
a one associates the elliptic curve
E
= C
/
a over
C
.An
O
/
a
is isomorphic to
E
. One can show that End(
E
)
Cl(
. The theory
of complex multiplication shows that
E
is defined over a number field (called the ring class
field) and has good reduction modulo the characteristic
p
of
O
) if and only if
C
=
O
F
q
. This correspondence is not
canonical, since the reduction modulo
p
map is not well-defined (it depends on a choice of
prime ideal above
p
in the ring class field).
Let a be an invertible
O
-ideal and
E
= C
/
a.Letl be an invertible
O
-ideal and, inter-
preting l
⊆
End(
E
), consider the set
E
[l]
={
P
∈
E
(
C
):
φ
(
P
)
=
O
E
for all
φ
∈
l
}
. Since
O
⊆ C
we can interpret l
, in which case
E
[l]
= {
⊆ C
z
∈ C
/
a :
αz
∈
a
,
for all
α
∈
l
}
=
l
−
1
a
/
a
.
It follows that #
E
[l] is equal to the norm of the ideal l. The identity map on
C
induces the
isogeny
/
l
−
1
a
C
/
a
→ C
with kernel l
−
1
a
/
a
=
,butthe
theory reduces well to elliptic curves over finite fields, and, indeed, every isogeny from
E
to an elliptic curve
E
with End(
E
)
E
[l]. The above remarks apply to elliptic curves over
C
End(
E
) arises in this way. This shows that not only
do ordinary elliptic curves correspond to ideals in
=
O
, but so do their isogenies.
=
∈ N
C
→
C
/
l
−
1
a is [
].
Exercise 25.3.4
Show that if l
(
) where
then the isogeny
/
a
→
E
O
=
O
Exercise 25.3.5
Suppose the prime
splits in
as (
)
l
1
l
2
in
.Let
φ
:
E
correspond to the ideal l
1
. Show that
φ
corresponds to l
2
.
O
K
= Z
[
θ
] if and only if the minimal polynomial of
θ
factors modulo
with two linear factors. If
D
is the discriminant of
K
then
splits if and
only if the Kronecker symbol satisfies (
D
)
Let
be a prime. Then
splits in
=+
1. Note that the Kronecker symbol is the
Legendre symbol when
is odd and
0
D
≡
0(mod4)
,
(
2
)
=
1
D
≡
1(mod8)
,
(25.4)
−
1
D
≡
5(mod8)
.
Let
E
be an elliptic curve over
F
q
with End(
E
)
=
O
and let
be coprime to the conductor
(
D
) prime ideals l above
, and so there are this many isogenies of
degree
from
E
. It follows there are
-isogenies in the isogeny graph for roughly half the
primes
.
Let
E
be an elliptic curve over
of
O
. There are 1
+
be a finite
set of primes that are all co-prime to the conductor. Let
G
be the component of
E
in the
isogeny graph
X
E,
F
q
,S
of Definition
25.3.1
.Let
S
={
l
1
,...,
l
k
}
F
q
corresponding to an
O
-ideal a.Let
S
⊆ N
be the set of classes of
S
invertible
) generated
by
S
. From the above discussion it follows that
G
can be identified with the graph whose
O
-ideals above primes
∈
S
and let
be the subgroup of Cl(
O
