Cryptography Reference
In-Depth Information
→
E
is
normalised
if
φ
∗
(
ω
E
)
Definition 25.1.10
An isogeny
φ
:
E
=
ω
E
.
Velu's formulae give a normalised isogeny. Note that normalised isogenies are incompat-
ible with Theorem
9.7.2
(which, for example, implies [
m
]
∗
(
ω
E
)
mω
E
). For this reason,
in many situations one needs to take an isomorphism from
E
to obtain the desired isogeny.
Example
25.1.12
shows how this works.
=
→
E
be an isogeny given by rational functions as in equa-
tion (
25.1
). Show that
φ
is normalised if and only if
c
Exercise 25.1.11
Let
φ
:
E
=
1.
Example 25.1.12
Let
E
:
y
2
+
xy
+
3
y
=
x
3
+
2
x
2
+
4
x
+
2 over
F
311
. Then
E
[2]
={
O
E
,
(
−
1
,
−
1)
,
(115
,
252)
,
(117
,
251)
}⊂
E
(
F
311
)
.
Let
G
=
E
[2]. Applying the Velu formulae one computes
t
(
G
)
=
8,
w
(
G
)
=
306,
A
1
=
1
,A
2
=
2
,A
3
=
3
,A
4
=
275 and
A
6
=
276. One can check that
E
and
E
:
Y
2
3
Y
2
X
3
2
X
2
+
XY
+
=
+
+
275
X
+
276
have the same
j
-invariant, but they are clearly not the same Weierstrass equation. Hence,
the Velu isogeny with kernel
E
[2] is not the isogeny [2] :
E
E
.
To recover the map [2] one needs to find a suitable isomorphism from
E
to
E
.The
isomorphism will have the form (
X,Y
)
→
(
u
2
X
r,u
3
Y
su
2
X
→
+
+
+
t
) where we must
have
u
1
/
2 to have the correct normalisation for the action of the isogeny on the invariant
differential (see Exercise
25.1.13
). One can verify that taking
r
=
67
gives the required isomorphism from
E
to
E
and that the composition of the Velu isogeny
and this isomorphism is the map [2].
=
291,
s
=
233 and
t
=
(
u
2
x
r,u
3
y
su
2
x
Exercise 25.1.13
Show that if
φ
:(
x,y
)
→
+
+
+
t
)isanisomorphism
from
E
to
E
then
φ
∗
(
ω
E
)
1
u
ω
E
.
Exercise 25.1.14
Determine the complexity of constructing and computing the Velu
isogeny. More precisely, show that if
d
=
=
#
G
and
G
⊂
E
(
F
q
n
) then
O
(
dM
(
n,q
)) bit
operations are sufficient, where
M
(
n,q
)
=
M
(
n
log(
nq
)) is the number of bit operations to
multiply two-degree
n
polynomials over
F
q
.
Further, show that if
d
is an odd prime then
n
≤
d
−
1 and so the complexity can be
written as
O
(
d
2
+
log(
q
)
1
+
) bit operations.
Example 25.1.15
Consider
E
:
y
2
x
3
=
+
2
x
over
F
37
, with
j
=
26
≡
1728 (mod 37).
5
2
We have #
E
(
F
37
giving a
2-isogeny from
E
.UsingVelu's formulae, one determines that the image of this isogeny is
E
1
:
y
2
F
37
)
=
2
·
so there is a unique point (0
,
0) of order 2 over
x
3
=
+
29
x
, which also has
j
-invariant 26 and is isomorphic to
E
over
F
37
.
∈ F
37
2
satisfy
α
2
Now consider the other points of order 2 on
E
.Let
α
=−
2. The
maps to
E
2
:
y
2
x
3
isogeny
φ
2
with kernel
{
O
E
,
(
α,
0)
}
=
+
28
αx
, while the isogeny
φ
3
maps to
E
3
:
y
2
x
3
with kernel
{
O
E
,
(
−
α,
0)
}
=
−
28
αx
. Note that there is an isomorphism
F
37
2
.Wehave
φ
2
◦
φ
3
◦
ψ
:
E
2
→
E
3
over
φ
2
=
φ
3
=
[2] on
E
. One can also consider
