Cryptography Reference
In-Depth Information
Exercise 9.1.5
Let
P
1
=
(
x
1
:
y
1
:
z
1
) and
P
2
=
(
x
2
:
y
2
:
z
2
) be points on the elliptic curve
E
:
y
2
z
x
3
a
4
xz
2
a
6
z
3
=
+
+
over
k
.Let
u
=
x
1
z
2
−
x
2
z
1
.
Show that (
x
3
:
y
3
:
z
3
) is a projective representation for
P
1
+
P
2
where
y
2
z
1
)
2
u
x
2
z
1
)
u
3
x
3
=
z
1
z
2
(
y
1
z
2
−
−
(
x
1
z
2
+
(9.4)
y
2
z
1
)
3
y
2
z
1
)
u
2
y
1
z
2
u
3
y
3
=−
z
1
z
2
(
y
1
z
2
−
+
(2
x
1
z
2
+
x
2
z
1
)(
y
1
z
2
−
−
(9.5)
z
1
z
2
u
3
z
3
=
(9.6)
(as long as the resulting point is not (0
,
0
,
0)).
The elliptic curve addition formula of equations (
9.3
) and (
9.4
)-(
9.6
) are undefined
on certain inputs (such as
P
P
1
) and so one currently needs to make
decisions (i.e., use “if” statements) to compute on elliptic curves. This does not agree
with the definition of an algebraic group (informally, that the group operation is given by
polynomial equations; formally that there is a morphism
E
=
O
E
or
P
2
=−
×
→
E
). However, it can be
shown (see Theorem III.3.6 of Silverman [
505
]) that elliptic curves are algebraic groups.
To
E
make
this
concrete
let
E
be
an
elliptic
curve
over
k
written
projectively.
A
complete system of addition laws
for
E
(
k
) is a set of triples of polynomials
{
(
f
i,x
(
x
1
,y
1
,z
1
,x
2
,y
2
,z
2
)
,f
i,y
(
x
1
,y
1
,z
1
,x
2
,y
2
,z
2
)
,f
i,z
(
x
1
,y
1
,z
1
,x
2
,y
2
,z
2
)) : 1
≤
i
≤
k
}
such that, for all points
P,Q
), at least one of (
f
i,x
(
P,Q
)
,f
i,y
(
P,Q
)
,f
i,z
(
P,Q
))
is defined and all triples defined at (
P,Q
) give a projective representation of the point
P
∈
E
(
k
Q
.
A rather surprising fact, due to Bosma and Lenstra [
87
], is that one can give a complete
system of addition laws for
E
(
+
) using only two triples of polynomials. The resulting
equations are unpleasant and not useful for practical computation.
k
9.2 Morphisms between elliptic curves
The goal of this section is to show that a morphism between elliptic curves is the composition
of a group homomorphism and a translation. In other words, all geometric maps between
elliptic curves have a group-theoretic interpretation.
Theorem 9.2.1
Let E
1
andE
2
be elliptic curves over
k
and let φ
:
E
1
→
E
2
be a morphism
of varieties such that φ
(
=
O
E
2
. Then φ is a group homomorphism.
Proof
(Sketch) The basic idea is to note that
φ
∗
:Pic
0
k
O
E
1
)
Pic
0
k
(
E
2
) (where Pic
0
k
(
E
1
)
→
(
E
i
)
denotes the degree zero divisor class group of
E
i
over
k
) is a group homomorphism and
φ
∗
((
P
)
−
(
O
E
1
))
=
(
φ
(
P
))
−
(
O
E
2
). We refer to Theorem III.4.8 of [
505
] for the details.
Definition 9.2.2
Let
E
be an elliptic curve over
k
and let
Q
∈
E
(
k
). We define the
translation map to be the function
τ
Q
:
E
→
E
given by
τ
Q
(
P
)
=
P
+
Q
.
