Cryptography Reference
In-Depth Information
for ordinary curves. Two facts are of crucial importance in Kohel's algorithm. The first
(Corollary
25.4.7
) is that one can recognise the floor when standing on it. The second fact is
that if one starts a chain of
-isogenies with a descending isogeny, and avoids backtracking,
then all the isogenies in the chain are descending.
Before going any further, we discuss how to compute a non-backtracking chain of
-
isogenies. Given
j
(
E
) one can compute the
j
-invariants of
-isogenous curves over
F
q
by computing the roots of
F
(
y
)
F
q
. Recall that one computes
(
x,y
)
in
O
(
3
+
) bit operations and finds the roots of
F
(
y
)in
=
(
j
(
E
)
,y
)in
F
q
in expected time bounded by
O
(
2
log(
)log(
q
)) operations in
j
(
E
) and let
j
1
be one of the roots of of
F
(
y
).
We want to find, if possible,
j
2
∈ F
q
such that there are
-isogenies from
E
to
E
1
(where
j
(
E
1
)
F
q
.Let
j
0
=
=
=
j
2
) and such that
j
2
=
j
0
(so the second
isogeny is not the dual of the first). The trick is to find roots of
(
j
1
,y
)
/
(
y
j
1
) and from
E
1
to
E
2
(where
j
(
E
2
)
j
0
). This
process can be repeated to compute a chain
j
0
,j
1
,j
2
,...
of
j
-invariants of
-isogenous
curves. As mentioned earlier, an alternative approach to walking in the isogeny graph is to
find
−
F
q
-rational factors of the
-division polynomial and use Velu's formulae; this is less
efficient in general and the method to detect backtracking is to compute the image curve
using Velu's formulae and then compute its
j
-invariant.
The basic idea of Kohel's algorithm is, for each prime
dividing
13
the conductor of
Z
[
π
q
], to find a chain of
-isogenies from
E
to an elliptic curve on the floor. Suppose
is a
prime and
m
c
. Kohel (on page 46 of [
315
]) suggests to take two non-backtracking chains
of
-isogenies of length at most
m
from
E
.If
E
is on the floor then this is immediately
detected. If
E
is not on the surface then at least one of the initial
-isogenies is descending,
so in at most
m
steps one finds oneself on the floor. So if after
m
steps neither chain of
isogenies has reached the floor then it follows that we must have started on the surface (and
some or all of the
-isogenies in the chain were along the surface). Note that, apart from
the algorithm for computing roots of polynomials, the method is deterministic.
Let
E
:
y
2
x
3
Exercise 25.4.10
=
+
3
x
+
6 over
F
37
be an elliptic curve. Note that
4 and 4
2
2
4
#
E
(
F
37
)
=
37
+
1
−
−
4
·
37
=−
·
7. Hence, the conductor is 4. We have
j
(
E
)
10. Using the modular polynomial one finds the following
j
-invariants of elliptic
curves 2-isogenous to
E
:11
,
29
,
31. Further, there is a single 2-isogeny from
j
-invariants
11
,
31 (in both cases, back to
j
=
=
10). But from 29 there is a 2-isogeny to
j
=
10 and two
2-isogenies to
j
29. What is End(
E
)? Give
j
-invariants for a curve on the floor and a
curve on the surface.
=
The worst case of Kohel's algorithm is when the conductor is divisible by one or more
very large primes
(since determining the
j
-invariant of an
-isogenous curve is polynomial
in
and so exponential in the input size). Since
c
can be as big as
√
q
the above method
(i.e., taking isogenies to the floor) would therefore have worst-case complexity of at least
q
1
/
2
bit operations (indeed, it would be
O
(
q
3
/
2
+
) operations in
F
q
if one includes the cost
of generating modular polynomials). Kohel (pages 53 to 57 of [
315
]) noted that, when
O
(
q
1
/
6
); see Exercise
12.5.1
.
13
It is necessary to find the square factors of
t
2
−
4
q
, which can be done in deterministic time
