Cryptography Reference
In-Depth Information
numbers given by short Weierstrass form
A
(
℘
(
z
))
B
(
℘
(
z
))
℘
(
βz
)
=
(25.3)
z
−
2
3
G
4
z
2
where
A
and
B
are polynomials and where
℘
(
z
)
is the Weierstrass
function (see Theorem VI.3.5 of Silverman [
505
]). This isogeny is not normalised (since
℘
(
βz
)
=
+
+···
β
−
2
z
−
2
it follows that the pullback of
ω
E
under
φ
is
βω
E
). Stark's idea
is to express
℘
as a (truncated) power series in
z
; the coefficients of this power series are
determined by the coefficients of the elliptic curve
E
. One computes
A
and
B
by taking
the continued fraction expansion of the left-hand side of equation (
25.3
). One can apply
this algorithm to curves over finite fields by applying the Deuring lifting theorem. Due
to denominators in the power series coefficients of
℘
(
z
) the method only works when
char(
=
+···
k
)
=
0 or
cha
r(
k
) is sufficiently large. Stark's paper [
522
] gives a worked example in
=
√
−
the case
β
2.
→
E
by
=
A
(
℘
E
(
z
))
/B
(
℘
E
(
z
)) where now the power series for
℘
E
(
z
) and
℘
E
(
z
) are different since the
elliptic curve equations are different. Note that it is necessary to have actual curve equations
for the normalised isogeny, not just
j
-invariants. We refer to Section 6.2 of Bostan, Morain,
Salvy and Schost [
88
] for further details and complexity estimates.
The
idea
generalises
to
normalised
isogenies
φ
:
E
writing
℘
E
(
z
)
25.2.3 The small characteristic case
As we have seen, the Elkies and Stark methods require the characteristic of the ground field
to be either zero or relatively large since they use lifting to short Weierstrass forms over
C
and since the power series expansions have rational coefficients that are divisible by various
small primes. Hence, there is a need for algorithms that handle the case when char(
k
)issmall
(especially, char(
2). A number of such methods have been developed by Couveignes,
Lercier, Morain and others. We briefly sketch Couveignes' “second method” [
143
].
Let
p
be the characteristic of the field. We assume that
p
is “small” (in the sense that
an algorithm performing
p
operations is considered efficient). Let
E
and
E
be ordinary
6
elliptic curves over
k
)
=
F
p
m
.
The basic idea is to use the fact that if
φ
:
E
→
E
is an isogeny of odd prime degree
p
(isogenies of degree
p
are easy: they are either Frobenius or Verschiebung) then
φ
maps points of order
p
k
on
E
to points of order
p
k
on
E
. Hence, one can try to determine
the rational functions describing
φ
by interpolation from their values on
E
[
p
k
]. One could
interpolate using any torsion subgroup of
E
, but using
E
[
p
k
] is the best choice since it is
a cyclic group and so there are only
ϕ
(
p
k
)
=
p
k
−
1
points to check (compared with
ϕ
(
n
2
)ifusing
E
[
n
]). The method can be applied to any elliptic curve
E
in the isomorphism
class, so in general it will not return a normalised isogeny.
=
p
k
−
6
The restriction to ordinary curves is not a significant problem. In practice, we are interested in elliptic curves over
F
p
m
where
m
is large, whereas supersingular curves are all defined over
F
p
2
. Indeed, for small
p
there are very few supersingular curves,
and isogenies of small degree between them can be computed by factoring division polynomials and using Velu's formulae.
