Cryptography Reference
In-Depth Information
of
X
0
(
)(
k
) corresponds to a pair (
E,G
) where
E
is an elliptic curve over
k
and where
G
is a cyclic subgroup of
E
, defined over
, of order
. Note that it is possible to have
an elliptic curve
E
together with two distinct cyclic subgroups
G
1
and
G
2
of order
such
that the image curves
E/G
1
and
E/G
2
are isomorphic; in this case (
E,G
1
) and (
E,G
2
)
are distinct points of
X
0
(
) but correspond to a repeated root of
(
j
(
E
)
,y
) (it follows
from the symmetry of
(
x,y
) that this is a singular point on the model). In other words,
a repeated root of
(
j
(
E
)
,y
) corresponds to non-equivalent
-isogenies from
E
to some
elliptic curve
E
.
Since there are
k
+
1 cyclic subgroups of
E
[
] it follows that
(
j
(
E
)
,y
) has degree
+
=
x
+
1
+
y
+
1
−
(
xy
)
+···
1. Indeed,
(
x,y
)
with all other terms of lower degree (see
Theorem 11.18 of Cox [
145
] or Theorem 3 of Section 5.2 of Lang [
328
]). The coefficients
of
(
x,y
) are large (as seen in Example
25.2.1
, even when
=
2 the coefficients are
large).
Example 25.2.1
x
3
y
3
x
2
y
2
1488(
x
2
y
xy
2
)
162000(
x
2
y
2
)
2
(
x,y
)
=
+
−
+
+
−
+
+
40773375
xy
+
8748000000(
x
+
y
)
−
157464000000000
.
Let
be prime. Cohen [
128
] showed that the number of bits in the largest coeffi-
cient of
(
x,y
)is
O
(
log(
)) (see Br oker and Sutherland [
103
] for a more precise
bound). Since there are roughly
2
coefficients it follows that
(
x,y
) can be written down
using
O
(
3
log(
)) bits, and it is believed that this space requirement cannot be reduced.
Hence, one expects to perform at least
O
(
3
log(
))
O
(
3
+
) bit operations
3
to compute
(
x,y
). Indeed, using methods based on modular functions, one can conjecturally
4
com-
pute
(
x,y
)in
O
(
3
+
) bit operations (see Enge [
179
]). Using modular functions other
than the
j
-function can lead to polynomials with smaller coefficients, but this does not
affect the asymptotic complexity.
The fastest method to compute modular polynomials is due to Broker, Lauter and
Sutherland [
102
]. This method exploits some of the ideas explained later in this chapter
(in particular, isogeny volcanoes). The method computes
(
x,y
) modulo small primes
and then determines
(
x,y
) by the Chinese remainder theorem. Under the Generalised
Riemann Hypothesis (GRH) the complexity is
O
(
3
log(
)
3
log(log(
))) bit operations. For
the rest of the chapter we abbreviate the cost as
O
(
3
+
) bit operations. The method can
also be used to compute
(
x,y
) modulo
p
, in which case the space requirements are
O
(
2
log(
)
2
=
2
log(
p
)) bits.
The upshot is that, given an elliptic curve
E
over
+
k
,the
j
-invariants of elliptic curves
E
that are
-isogenous over
k
(where gcd(
,
char(
k
))
=
1) are given by the roots of
(
j
(
E
)
,y
)in
k
. When
E
is ordinary, Theorem
25.4.6
implies that
(
j
(
E
)
,y
) has either
0
,
1
,
2or
+
1 roots in
k
(counted with multiplicities).
3
Recall that a function
f
(
)is
O
(
3
+
) if, for every
>
0, there is some
C
(
)
,L
(
)
∈ R
>
0
such that
f
(
)
<C
(
)
3
+
for all
>L
(
).
4
Enge needs an assumption that rounding errors do not affect the correctness of the output.
