Cryptography Reference
In-Depth Information
Exercise 25.1.19
Let the notation be as in Lemma
25.1.16
.For1
≤
i
≤
3 define
1
S
i
=
x
Q
)
i
.
(
x
−
Q
∈
G
1
ψ
(
x
)
/ψ
(
x
) and that
S
2
=−
(
ψ
(
x
)
/ψ
(
x
))
=
((
ψ
(
x
)
)
2
ψ
(
x
)
ψ
(
x
)
)
/
Show that
S
1
=
−
ψ
(
x
)
2
.
Exercise 25.1.20
Complete the proof of Lemma
25.1.16
.
Exercise 25.1.21
Determine the complexity of using Lemma
25.1.16
to compute isogenies
over finite fields. More precisely, show that if
G
⊆
E
(
F
q
n
) is defined over
F
q
and
d
=
#
G
then one can compute
ψ
(
x
)in
O
(
d
2
) operations in
∈ F
q
[
x
] is computed
show that one can compute the polynomials
A
(
x
) and
B
(
x,y
) for the isogeny in
O
(
d
)
operations in
F
q
. Once
ψ
(
x
)
F
q
.
25.2 Isogenies from
j
-invariants
Velu's formulae require that one knows the kernel of the desired isogeny. But in some
applications one wants to take a
k
-rational isogeny of a given degree
d
(assuming such
an isogeny exists) from
E
to another curve
E
(where
E
may or may not be known), and
one does not know a specific kernel. By Theorem
25.1.2
one can restrict to the case when
d
=
is prime. We usually assume that
is odd, since the case
=
2 is handled by points
of order 2 and Velu's formulae.
One solution is to choose a random point
P
-rational subgroup
of order
. To find such a point, compute the
-division polynomial (which has degree
(
2
∈
E
[
] that generates a
k
1)
/
2.
Roots of such factors are points of order
, and one can determine whether or not they
generate a
−
1)
/
2 when
is odd) and find irreducible factors of it in
k
[
x
]ofdegreeupto(
−
-rational subgroup by computing all points in the subgroup. Roots of factors
of degree
d>
(
k
-rational subgroups of order
. This approach
is expensive when
is large for a number of reasons. For a start, finding roots of degree at
most (
−
1)
/
2 cannot give rise to
k
1)
/
2 of a polynomial of degree (
2
F
q
[
x
] takes
(
3
log(
)log(
q
)) bit
−
−
1)
/
2in
operations.
A more elegant approach is to use the
th modular polynomial. It is beyond the scope
of this topic to present the theory of modular functions and modular curves (some basic
references are Sections 5.2 and 5.3 of Lang [
328
] and Section 11.C of Cox [
145
]). The
fundamental fact is that there is a symmetric polynomial, called the
modular polynomial
2
(
x,y
)
and
E
is an elliptic
∈ Z
[
x,y
] such that if
E
is an elliptic curve over a field
k
curve over
k
then there is a separable isogeny of degree
(where gcd(
,
char(
k
))
=
1) with
cyclic kernel from
E
to
E
if and only if
(
j
(
E
)
,j
(
E
))
0 (see Theorem 5, Section 5.3 of
Lang [
328
]). The modular polynomial
(
x,y
) is a singular model for the modular curve
X
0
(
) over
=
Q
. This modular curve is a moduli space in the sense that a (non-cusp) point
2
The reader should not confuse the modular polynomial
(
x,y
) with the cyclotomic polynomial
m
(
x
).
