Cryptography Reference
In-Depth Information
E
[
p
k
]
E
[
p
k
−
1
] and
Couveignes' method is
as
follows: first, compute points
P
∈
−
P
∈
E
[
p
k
]
−
E
[
p
k
−
1
] over
=
P
. Then try to determine the rational
F
p
and guess that
φ
(
P
)
x
([
i
]
P
); if this does not work
then try another guess for
P
. The interpolation is done as follows (we assume
p
k
>
2
).
First, compute a polynomial
A
(
x
)ofdegree
d
where 2
<d
function
φ
1
(
x
)
=
u
(
x
)
/v
(
x
) by interpolating
φ
1
(
x
([
i
]
P
))
=
p
k
such that
A
(
x
([
i
]
P
))
≤
=
=
i
=
1
(
x
x
([
i
]
P
)for1
x
([
i
]
P
)). If the guess for
P
is
≤
i
≤
d
. Also compute
B
(
x
)
−
correct then
A
(
x
)
≡
u
(
x
)
/v
(
x
)(mod
B
(
x
)) where deg(
u
(
x
))
=
,
deg(
v
(
x
))
=
−
1 and
v
(
x
) is a square. Writing this equation as
A
(
x
)
v
(
x
)
B
(
x
)
w
(
x
) it follows that
u
(
x
)
and
v
(
x
) can be computed using Euclid's algorithm. The performance of the algorithm
depends on the method used to determine points in
E
[
p
k
], but is dominated by the fact
that these points lie in an extension of the ground field of large degree, and that one
expects to try around
=
u
(
x
)
+
choices for
P
before hitting the right one. The complexity is
polynomial in
,p
and
m
(where
E
is over
1
2
p
k
≈
2 the fastest method was given
by Lercier [
344
]. For further details we refer to the surveys by Lercier and Morain [
345
]
and De Feo [
185
].
F
p
m
). When
p
=
25.3 Isogeny graphs of elliptic curves over finite fields
Let
E
be an elliptic curve over
F
q
.The
F
q
-
isogeny class
of
E
is the set of
F
q
-isomorphism
classes of elliptic curves over
F
q
that are isogenous over
F
q
to
E
. Tate's isogeny theorem
states that two elliptic curves
E
and
E
over
F
q
are
F
q
-isogenous if and only if #
E
(
F
q
)
=
#
E
(
F
q
) (see Theorem
9.7.4
for one implication).
We have seen in Sections
9.5
and
9.10
that the number of
F
q
-iso
m
orphism classes
F
q
is roughly 2
q
and that there are roughly 4
√
q
possible values
of elliptic curves over
for #
E
(
F
q
). Hence, if isomorphism
c
lasses were distributed uniformly across all group
orders one would expect around
2
√
q
elliptic curves in each isogeny class. The theory of
complex multiplication gives a more precise result (as mentioned in Section
9.10.1
). We
denote by
π
q
the
q
-power Frobenius map; see Section
9.10
for its properties. The number
of
1
F
q
-isomorphism classes of ordinary elliptic curv
es over
F
q
with
q
+
1
−
t
points is the
t
2
Hurwitz class number of the ring
Z
[
π
q
]
= Z
[(
t
+
−
4
q
)
/
2]. This is the sum of the ideal
class numbers
h
(
⊆
O
⊆
O
K
. It follows (see Remark
9.10.19
) that
there are
O
(
q
1
/
2
log(
q
) log(log(
q
))) elliptic curves in each isogeny class. For supersingular
curves see Theorem
9.11.11
.
O
) over all orders
Z
[
π
q
]
Definition 25.3.1
Let
E
be an elliptic curve over a field
k
of characteristic
p
.Let
S
⊆ N
be a finite set of primes. Define
X
E,
k
,S
to be the (directed) graph
7
-isogeny class of
E
. Vertices are
typically labelled by
j
(
E
), though we also speak of “the vertex
E
”.
8
with vertex set being the
k
There is a (directed)
7
Some authors would use the name “multi-graph”, since there can be loops and/or multiple edges between vertices.
8
In the supersingular case one can label vertices as
j
(
E
) without ambiguity only when
k
is algebraically closed: when
k
is finite
then, in the supersingular case, one has two distinct vertices in the graph for
E
and its quadratic twist. For the ordinary case
there is no ambiguity by Lemma
9.11.12
(also see Exercise
25.3.8
).
