Cryptography Reference
In-Depth Information
Show that if char(
k
)
=
2 then (
x,y
) has order 2 if and only if 2
y
+
a
1
x
+
a
3
=
0. Show
that this is also equivalent to
4
x
3
(
a
1
+
4
a
2
)
x
2
(
a
3
+
+
+
(2
a
1
a
3
+
4
a
4
)
x
+
4
a
6
)
=
0
.
(9.9)
Note that when
a
1
=
0 this polynomial is simply 4 times the right-hand side of the
elliptic curve equation. Show that this polynomial has distinct roots and so if char(
a
3
=
k
)
=
2
then #
E
[2]
=
4.
Lemma 9.6.11
Let E and E be elliptic curves over
k
.Ifn
∈ N
then
[
n
]
is not the zero
isogeny. Further,
Hom
k
(
E,E
)
is torsion-free as a
Hom
k
(
E,E
)
is
Z
-module (i.e., if φ
∈
non-zero then
[
n
]
◦
φ is non-zero for all n
∈ Z
, n
=
0
) and
End
k
(
E
)
has no zero divisors.
→
E
are non-zero isogenies
s
uch that [0]
Proof
First, suppose
φ
1
,φ
2
:
E
=
φ
1
◦
φ
2
.By
Theorem
9.6.3
,
φ
1
,φ
2
and hence
φ
1
◦
. Since the zero isogeny is
not surjective it follows that there are no zero divisors in End
k
(
E
).
Now, consider any
n
φ
2
are surjective over
k
2
k
m
f
or
some
k
∈ N
and note that
n
=
∈ Z
≥
0
and some odd
m
∈ N
.
k
k
=
By Exercise
9.6.10
we know that [2] is not zero over
(when char(
)
2 this is immediate
k
=
since there are at most three points of order 2; when char(
2 one must show that if
equation (
9.9
) is identically zero then the Weierstrass equation is singular). It follows that
[2
k
]
)
=
[2]
◦
[2]
◦···◦
[2] is not zero either (since if [2] is non-zero then it is surjective
on
E
(
k
)). Finally, since there exists
P
∈
E
(
k
) such that
P
=
O
E
but [2]
P
=
O
E
we have
[2
k
]isnot
[
m
]
P
=
P
=
O
E
and so [
m
] is not the zero isogeny. It follows that [
n
]
=
[
m
]
◦
the zero isogeny.
Similarly, if [0]
Hom
k
(
E,E
) then either [
n
]or
φ
is the zero isogeny.
=
[
n
]
φ
for
φ
∈
a
6
and E
:
Y
2
Lemma 9.6.12
Let E
:
y
2
x
3
a
2
x
2
+
a
1
xy
+
a
3
y
=
+
+
a
4
x
+
+
a
1
XY
+
→
E be an isogeny of
X
3
a
2
X
2
a
3
Y
=
+
+
a
4
X
+
a
6
be elliptic curves over
k
. Let φ
:
E
elliptic curves over
k
. Then φ may be expressed by a rational function in the form
=
+
φ
(
x,y
)
(
φ
1
(
x
)
,yφ
2
(
x
)
φ
3
(
x
))
where
2
φ
3
(
x
)
=−
a
1
φ
1
(
x
)
−
a
3
+
(
a
1
x
+
a
3
)
φ
2
(
x
)
.
In particular, if
char(
k
)
=
2
anda
1
=
a
3
=
a
1
=
a
3
=
0
thenφ
3
(
x
)
=
0
, while if
char(
k
)
=
2
then φ
2
(
x
)
=
(
a
1
φ
1
(
x
)
+
a
3
)
/
(
a
1
x
+
a
3
)
.
Proof
Certainly,
φ
may be written as
φ
(
x,y
)
=
(
φ
1
(
x
)
+
yf
(
x
)
,yφ
2
(
x
)
+
φ
3
(
x
)) where
φ
1
(
x
)
,f
(
x
)
,φ
2
(
x
) and
φ
3
(
x
) are rational functions.
Since
φ
is a group homomorphism it satisfies
φ
(
−
P
)
=−
φ
(
P
). Writing
P
=
(
x,y
)the
left-hand side is
φ
(
−
(
x,y
))
=
φ
(
x,
−
y
−
a
1
x
−
a
3
)
=
(
φ
1
(
x
)
+
(
−
y
−
a
1
x
−
a
3
)
f
(
x
)
,
(
−
y
−
a
1
x
−
a
3
)
φ
2
(
x
)
+
φ
3
(
x
))