Cryptography Reference
In-Depth Information
Exercise 7.9.6
Prove that the following algebraic formulae for the chord-and-tangent
rule are correct. Let
P
1
,P
2
∈
E
(
k
), we want to compute
S
=
P
1
+
P
2
.If
P
1
=
O
E
then
S
=
P
2
and if
P
2
=
O
E
then
S
=
P
1
. Hence, we may now assume that
P
1
=
(
x
1
,y
1
) and
P
2
=
(
x
2
,y
2
) are affine. If
y
2
=−
y
1
−
H
(
x
1
) then
S
=
O
E
. Otherwise, set
λ
to be as in
λ
2
Definition
7.9.1
and compute
x
3
=
+
a
1
λ
−
a
2
−
x
1
−
x
2
and
y
3
=−
λ
(
x
S
−
x
1
)
−
y
1
.
The sum is
S
=
(
x
3
,y
3
).
Before proving the main theorem, we state the following technical result, whose proof
is postponed to the next chapter (Corollary
8.6.5
).
Theorem 7.9.7
Let P
1
,P
2
∈
k
)
be a points on an elliptic curve such that P
1
=
E
(
P
2
. Then
−
(
P
1
)
(
P
2
)
is not a principal divisor.
We now consider the divisor class group Pic
0
k
(
E
). The following result is usually obtained
as a corollary to the Riemann-Roch theorem, but we give an ad-hoc proof for elliptic curves.
One can consider this result as the Abel-Jacobi map in the case of genus 1 curves.
)
and
Pic
0
k
Theorem 7.9.8
There is a one-to-one correspondence between E
(
k
(
E
)
, namely
P
→
(
P
)
−
(
O
E
)
.
Proof
We first show that the map is injective. Suppose (
P
1
)
−
(
O
E
)
≡
(
P
2
)
−
(
O
E
). Then
(
P
1
)
−
(
P
2
) is principal, and so Theorem
7.9.7
implies
P
1
=
P
2
.
=
P
n
P
(
P
) be any effective divisor
on
E
. We prove that
D
is equivalent to a divisor of the form
It remains to show that the map is surjective. Let
D
(
P
)
+
(deg(
D
)
−
1)(
O
E
)
.
(7.10)
We will do this by replacing any term (
P
1
)
+
(
P
2
) by a term of the form (
S
)
+
(
O
E
)for
some point
S
.
The key equations are (
P
)
+
(
ι
(
P
))
=
2(
O
E
)
+
div(
v
(
x
)) where
v
(
x
) is as in Defini-
tion
7.9.1
,or,if
P
1
=
ι
(
P
2
), (
P
1
)
+
(
P
2
)
=
(
S
)
+
(
O
E
)
+
div(
l
(
x,y
)
/v
(
x
)). The first equa-
tion allows us to replace any pair (
P
)
+
(
ι
(
P
)), including the case
P
=
ι
(
P
), by 2(
O
E
). The
second equation allows us to replace any pair (
P
1
)
+
(
P
2
), where
P
1
=
ι
(
P
2
) (but including
the case
P
1
=
O
E
). It is clear that any pair of affine points is included in
one of these two cases, and so repeating these operations a finite number of times reduces
any effective divisor to the form in equation (
7.10
).
Finally, let
D
be a degree zero divisor on
E
. Write
D
P
2
) with (
S
)
+
(
D
2
where
D
1
and
D
2
are effective divisors of the same degree. By the above argument, we can write
D
1
≡
(
S
1
)
=
D
1
−
(
S
2
).
Finally, adding the divisor of the vertical line function through
S
2
and subtracting the divisor
of the line between
S
1
and
ι
(
S
2
)gives
D
+
(deg(
D
1
)
−
1)(
O
E
) and
D
2
≡
(
S
2
)
+
(deg(
D
1
)
−
1)(
O
E
). Hence,
D
≡
(
S
1
)
−
≡
(
S
)
−
(
O
E
) for some point
S
as required.
) is in bijection with the group Pic
0
k
) is a group, with the
group law coming from the divisor class group structure of
E
. It remains to show that the
group law is just the chord-and-tangent rule. In other words, this result shows that the chord-
and-tangent rule is associative. Note that many texts prove that both
E
(
Since
E
(
k
(
E
) it follows that
E
(
k
) and Pic
0
k
k
(
E
)are
