Cryptography Reference
In-Depth Information
coefficients of
E
)
a
3
)
φ
1
(
x
)
.
2
φ
3
(
x
)
=−
a
1
φ
1
(
x
)
−
a
3
+
(
a
1
x
+
Lemma
9.6.13
showed that if
φ
1
(
x
)
=
a
(
x
)
/b
(
x
) in equation (
25.1
) then the degree of
φ
is max
{
deg
x
(
a
(
x
))
,
deg
x
(
b
(
x
))
}
. The kernel of an isogeny
φ
with
φ
1
(
x
)
=
a
(
x
)
/b
(
x
)is
{
O
E
}∪{
P
=
(
x
P
,y
P
)
∈
E
(
k
):
b
(
x
P
)
=
0
}
. The kernel of a separable isogeny of degree
d
has
d
elements.
Let
E
be an elliptic curve over a field
k
and
G
a finite subgroup of
E
(
k
) that is defined
. Theorem
9.6.19
states that there is a unique elliptic curve
E
(up to isomorphism)
and a separable isogeny
φ
:
E
over
k
→
E
over
k
such that ker(
φ
)
=
G
. We sometimes write
E
=
k
=
E/G
.Let
be a prime such that gcd(
,
char(
))
1. Since
E
[
] is isomorphic (as a
+
group) to the product of two cyclic groups, there are
1 different subgroups of
E
[
]of
order
. It follows that there are
+
1 isogenies of degree
, not necessarily defined over
k
, from
E
to other curves (some of these isogenies may map to the same image curve).
As implied by Theorem
9.6.18
and discussed in Exercise
9.6.20
, an isogeny is essen-
tially determined by its kernel. We say that two separable isogenies
φ
1
,φ
2
:
E
→
E
are
equivalent isogenies
if ker(
φ
1
)
=
ker(
φ
2
).
→
E
be a separable isogeny. Show that if
λ
Aut(
E
) then
λ
Exercise 25.1.1
Let
φ
:
E
∈
◦
φ
is equivalent to
φ
. Explain why
φ
◦
λ
is not necessarily equivalent to
φ
for
λ
∈
Aut(
E
).
Theorem
25.1.2
shows that isogenies can be written as “chains” of prime-degree iso-
genies. Hence, in practice, one can restrict to studying isogenies of prime degree. This
observation is of crucial importance in the algorithms.
Theorem 25.1.2
Let E and E be elliptic curves over
→
E be a separable
k
and let φ
:
E
isogeny that is defined over
k
. Then φ
=
φ
1
◦···◦
φ
k
◦
[
n
]
where φ
1
,...,φ
k
are isogenies
n
2
i
=
1
deg(
φ
i
)
.
of prime degree that are defined over
k
and
deg(
φ
)
=
Proof
Theorem
9.6.19
states that
φ
is essentially determined by its kernel subgroup
G
and
that
φ
is defined over
if and only if
G
is. We will also repeatedly use Theorem
9.6.18
,
which states that an isogeny
φ
:
E
k
→
E
defined over
k
factors as
φ
=
φ
2
◦
φ
1
(where
E
1
and
φ
2
:
E
1
→
E
are isogenies over
φ
1
:
E
→
k
) whenever ker(
φ
) has a subgroup
G
=
.
First, let
n
be the largest integer such that
E
[
n
]
ker(
φ
1
) defined over
k
φ
◦
⊆
G
=
ker(
φ
) and note that
φ
=
[
n
]
where [
n
]:
E
→
E
is the usual multiplication by
n
map. Set
i
=
1, define
E
0
=
E
and set
G
=
G/E
[
n
]. Now, let
|
#
G
be a prime and let
P
∈
G
have pri
me
order
. There is an
isogeny
φ
i
:
E
i
−
1
→
E
i
of degree
with kernel
P
.Let
σ
∈
Gal(
k
/
k
). Since
σ
(
P
)
∈
G
but
E
[
]
⊆
G
it follows that
σ
(
P
)
∈
P
and so
P
is defined over
k
. Hence, it follows
. Replace
G
by
φ
i
(
G
)
=
that
φ
i
is defined over
k
G/
P
and repeat the argument.
Exercise 25.1.3
How must the statement of Theorem
25.1.2
be modified if the requirement
that
φ
be separable is removed?
