Cryptography Reference
In-Depth Information
φ
3
◦
ψ
◦
φ
2
on
E
, which must be an element of End(
E
)
= Z
[
i
] of degree 4. One can show
that it is
i
[2] where
i
(
x,y
)
=
(
−
x,
31
y
).
Kohel [
315
] and Dewaghe [
158
] independently gave formulae for the Velu isogeny in
terms of the coefficients of the polynomial defining the kernel, rather than in terms of the
points in the kernel. We give these formulae in Lemma
25.1.16
for the case where
G
has
odd order (they are also given in Section 2.4 of [
315
]). Since a
k
-rational subgroup of an
elliptic curve can have points defined over an extension of
, working with the coefficients
of the polynomial can be more efficient than working with the points in
G
.
k
Lemma 25.1.16
Le
t
E
:
y
2
x
3
a
2
x
2
+
(
a
1
x
+
a
3
)
y
=
+
+
a
4
x
+
a
6
be an elliptic curve
over
k
. Let G
⊆
E
(
k
)
be a cyclic group of odd order
2
d
+
1
. Let G
1
⊆
G be such that
#
G
1
=
d and G
={
O
E
}∪
G
1
∪{−
Q
:
Q
∈
G
1
}
. Define
x
d
s
1
x
d
−
1
s
2
x
d
−
2
1)
d
s
d
ψ
(
x
)
=
(
x
−
x
Q
)
=
−
+
+···+
(
−
(25.2)
Q
∈
G
1
where the s
i
are the ith symmetric polynomials in the roots of ψ
(
x
)
(equivalently, in
the x-coordinates of elements of G
1
). Define b
2
=
a
1
+
4
a
2
,b
4
=
2
a
4
+
a
1
a
3
and b
6
=
E, with
ker(
φ
)
a
3
+
4
a
6
. Then there is an isogeny φ
:
E
→
=
G,oftheformφ
(
x,y
)
=
(
A
(
x
)
/ψ
(
x
)
2
,B
(
x,y
)
/ψ
(
x
)
3
)
where A
(
x
)
and B
(
x,y
)
are polynomials. Indeed
A
(
x
)
ψ
(
x
)
2
=
b
6
)(
ψ
(
x
)
/ψ
(
x
))
(4
x
3
b
2
x
2
(2
d
+
1)
x
−
2
s
1
−
+
+
2
b
4
x
+
(6
x
2
b
4
)(
ψ
(
x
)
/ψ
(
x
))
.
−
+
b
2
x
+
The proof of Lemma
25.1.16
is given as a sequence of exercises.
Exercise 25.1.17
Let the notation be as in Lemma
25.1.16
.Let
F
x
(
Q
),
F
y
(
Q
),
t
(
Q
) and
u
(
Q
) be as in Theorem
25.1.6
. Show that
6
x
Q
+
4
x
Q
+
b
2
x
Q
+
t
(
Q
)
=
b
2
x
Q
+
b
4
and
u
(
Q
)
=
2
b
4
x
Q
+
b
6
.
Exercise 25.1.18
Let the notation be as in Lemma
25.1.16
.Let
F
x
(
Q
),
F
y
(
Q
),
t
(
Q
) and
u
(
Q
) be as in Theorem
25.1.6
. Show that
x
Q
x
x
Q
=
x
Q
−
1
,
x
−
x
−
x
Q
x
1
x
Q
)
2
=
−
x
Q
)
,
(
x
−
(
x
−
x
Q
)
2
(
x
−
x
Q
x
2
x
Q
)
=
x
Q
−
x
−
x
Q
,
(
x
−
x
−
x
Q
x
2
2
x
x
Q
)
2
=
−
x
Q
)
+
1
,
(
x
−
(
x
−
x
Q
)
2
(
x
−
x
Q
x
3
3
x
2
x
Q
)
2
=
−
x
Q
)
+
2
x
+
x
Q
.
(
x
−
(
x
−
x
Q
)
2
(
x
−
