Cryptography Reference
In-Depth Information
Exercise 25.2.2
Given the polynomial
(
x,y
) and a value
j
∈ F
q
show that one can
∈ F
q
[
y
]in
O
(
2
(
log(
) log(
q
)
compute
F
(
y
)
=
(
j,y
)
+
M
(log(
q
)))) bit operations.
Show also that one can then compute the roots ˜
(
j
(
E
)
,y
) (or determine
that there are no roots) in expected time bounded by
O
(
2
log(
)log(
q
)) field operations
(which is
O
(
2
+
log(
q
)
3
) bit operations).
∈ F
q
of
F
(
y
)
=
→
E
For the rest of this section we consider algorithms to compute an
-isogeny
φ
:
E
given an elliptic curve
E
and the
j
-invariant of
E
.
F
q
and let
E
over
Exercise 25.2.3
Let
E
be an elliptic curve over
F
q
be a twist of
E
.
Show that there is an
F
q
-rational isogeny of degree
from
E
(to some elliptic curve) if and
F
q
-rational isogeny of degree
from
E
. Show that End(
E
)
=
End(
E
)
only if there is an
(where
=
denotes ring isomorphism).
25.2.1 Elkies' algorithm
Let
>
2beaprimeandlet
E
be an elliptic curve over
k
where char(
k
)
=
0 or char(
k
)
>
one constructs isogenies
using the naive method or the methods of the following sections). Let ˜
+
2. Assume
j
(
E
)
=
0
,
1728 (for the case
j
(
E
)
∈{
0
,
1728
}
∈ k
be such that
(
j
(
E
)
,
˜
)
0. We also assume that ˜
is a simple root of
(
j
(
E
)
,y
) (more precisely,
(
∂
(
x,y
)
/∂x
)(
j,
˜
)
=
=
0 and (
∂
(
x,y
)
/∂y
)(
j,
˜
)
=
0); see page 248 of Schoof [
477
]for
a discussion of why this condition is not too severe.
Elkies gave a method to determine an explicit equation for an elliptic curve
E
, such
that
j
(
E
)
˜
, and a polynomial giving the kernel of an
-isogeny from
E
to
E
. Elkies'
original motivation (namely, algorithms for point counting) only required computing the
kernel polynomial of the isogeny, but, as we have seen, from this information one can easily
compute the rational functions describing the isogeny. The method also works when
>
2
is composite, but that is not of practical relevance. The condition that char(
=
k
) not be small
(if it is non-zero) is essential.
We use the same notation as in Lemma
25.1.16
:
ψ
(
x
) is the polynomial of degree
(
1)
/
2 whose roots are the
x
-coordinates of affine points in the kernel
G
of the isogeny
and
s
i
are the
i
-th symmetric polynomials in these roots. We also define
−
x
i
P
p
i
=
P
∈
G
−{
O
E
}
2(
s
1
−
so that
p
1
=
2
s
2
) (these are Newton's formulae; see Lemma
10.7.6
).
While the value ˜
specifies the equation for the isogenous curve
E
(up to isomorphism)
it does not, in general, determine the isogeny (see pages 37 and 44 of Elkies [
178
]for
discussion). It is necessary to have some extra information, and for this the coefficient
p
1
suffices and can be computed using partial derivatives of the modular polynomial (this is
why the condition on the partial derivatives is needed).
The explanation of Elkies' algorithm requires theory that we do not have space to present.
We refer to Schoof [
477
] for a good summary of the details (also see Elkies [
178
] for further
2
s
1
and
p
2
=
