Cryptography Reference
In-Depth Information
Exercise 25.1.4
Let
E
be an ordinary elliptic curve. Let
φ
1
:
E
→
E
1
and
φ
2
:
E
1
→
E
2
be non-zero separable isogenies over
k
of coprime degrees
e
and
f
respectively. Show that
there is an elliptic curve
E
1
over
→
E
1
k
, and a pair of non-zero separable isogenies
ψ
1
:
E
and
ψ
2
:
E
1
→
E
2
of degrees
f
and
e
respectively, such that
φ
2
◦
φ
1
=
ψ
2
◦
ψ
1
.
25.1.1 Velu's formulae
We now present explicit formulae, due to Velu [613], for computing a separable isogeny
from an elliptic curve
E
with given kernel
G
. These formulae work in any characteristic.
As motivation for Velu's formulae, we now revisit Example
9.6.9
.
Example 25.1.5
Let
E
:
y
2
x
3
x
and consider the subgroup of order 2 generated by
the point (0
,
0). From Example
9.2.4
we know that the translation by (0
,
0) map is given by
=
+
1
.
x
,
−
y
x
2
τ
(0
,
0)
(
x,y
)
=
Hence, it follows that functions invariant under this translation map include
(
x
2
y/x
2
y
(
x
2
1)
/x
2
.
X
=
x
+
1
/x
=
+
1)
/x,
Y
=
y
−
=
−
One can compute that
X
3
=
(
x
6
+
3
x
4
+
3
x
2
+
1)
/x
3
and so
Y
2
y
2
(
x
2
1)
2
/x
4
=
−
(
x
6
x
4
x
2
1)
/x
3
=
−
−
+
X
3
=
−
4
X.
It follows that the map
x
2
,y
x
2
+
1
−
1
φ
(
x,y
)
=
x
x
2
is an isogeny from
E
to
E
:
Y
2
X
3
4
X
.
We remark that
φ
can also be written as
=
−
y
2
x
2
,y
x
2
−
1
φ
(
x,y
)
=
x
2
and can be written projectively as
(
x
(
x
2
z
2
):
y
(
x
2
z
2
):
x
2
z
)
φ
(
x
:
y
:
z
)
=
+
−
(
y
(
x
2
z
2
):
xy
2
x
2
z
z
3
=
+
−
−
:
xyz
)
(
y
2
z
:
y
(
x
2
z
2
):
x
2
z
)
=
−
(
xy
2
:
y
(
y
2
2
xz
):
x
3
)
.
=
−
Theorem 25.1.6
(Velu) Let E be an elliptic curve over
k
defined by the polynomial
a
6
−
y
2
a
3
y
=
x
3
a
2
x
2
F
(
x,y
)
=
+
+
a
4
x
+
+
a
1
xy
+
0
.
