Cryptography Reference
In-Depth Information
discussion). The basic idea is to use the fact (Deuring lifting theorem) that the isogeny lifts
to an isogeny between elliptic curves over
C
. One can then interpret the
-isogeny in terms
of Tate curves
5
C
∗
/q
Z
(we have not presented the Tate curve in this topic; see Section C.14
of [
505
] or Section 5.3 of [
506
]) as a map from
q
(
z
)to
q
(
z
)
. As discussed on page 40 of
Elkies [
178
], this isogeny is not normalised. There are a number of relations between the
modular
j
-function, certain Eisenstein series, the equation of the elliptic curve (in short
Weierstrass form) and the kernel polynomial of the isogeny. These relations give rise to
formulae that must also hold over
k
. Hence, one can work entirely over
k
and obtain the
kernel polynomial.
The details of this approach are given in Sections 7 and 8 of Schoof [
477
]. In particular,
Theorem 7.3 shows how to get
j
(derivative); Proposition 7.1 allows one to compute
the coefficients of the elliptic curve; Proposition 7.2 gives the coefficient
p
1
of the kernel
polynomial (which is a function of values specified in Proposition 7.1 and Theorem 7.3). The
coefficients of the kernel polynomial are related to the coefficients of the series expansion
of the Weierstrass
ζ
-function (see Theorem 8.3 of [
477
]).
The algorithm is organised as follows (see Algorithm
27
). One starts with an ordi-
nary elliptic curve
E
:
y
2
x
3
=
+
Ax
+
B
over
k
and
j
=
j
(
E
). We assume that
j
∈
(
∂
(
∂
{
0
,
1728
}
and char(
k
)
=
0 or char(
k
)
>
+
2. Let
φ
x
=
∂x
)(
j,
˜
),
φ
y
=
∂y
)(
j,
˜
),
(
∂
2
(
∂
2
(
∂
2
φ
xx
=
∂x∂y
)(
j,
˜
). One computes the deriva-
tive
j
and the corresponding values for
E
4
and
E
6
.Given ˜
, one computes ˜
and then
the coefficients
A
and
B
of the image curve
E
. Finally, one computes
p
1
, from which it is
relatively straightforward to compute all the coefficients of the kernel polynomial
ψ
(
x
).
∂x
2
)(
j,
˜
),
φ
yy
=
∂y
2
)(
j,
˜
) and
φ
xy
=
Exercise 25.2.4
Show that Elkies' algorithm requires
O
(
d
2
)
=
O
(
2
) operations in
k
.
Bostan, Morain, Salvy and Schost [
88
] have given algorithms (exploiting fast arithmetic
on power series) based on Elkies' methods. The algorithms apply when the characteristic
of the field is zero or is sufficiently large compared with
. There is a slight difference in
scope: Elkies' starts with only
j
-invariants whereas Bostan
et al.
assume that one is given
elliptic curves
E
and
E
in short Weierstrass form such that there is a normalised isogeny
of degree
over
from
E
to
E
. In general, one needs to perform Elkies' method before
one has such an equation for
E
and so the computations with modular curves still dominate
the cost. Theorem 2 of [
88
] states that one can compute the rational functions giving the
isogeny in
O
(
M
(
)) operations in
k
1 and when the coefficient
p
1
is
known. Note that Bostan
et al.
are not restricted to prime degree isogenies. An application
of the result of Bostan
et al.
is to determine whether there is a normalised isogeny from
E
to
E without
needing to compute modular polynomials. Lercier and Sirvent [
346
] (again,
assuming one is given explicit equations for
E
and
E
such that there is a normalised
-
isogeny between them) have shown how to achieve a similarly fast method even when the
characteristic of the field is small.
k
when char(
k
)
>
2
−
5
The notation
q
here refers to
q
(
z
)
=
exp(2
πiz
) and not a prime power.
