Cryptography Reference
In-Depth Information
We already know that
x
1
and
x
2
are roots of this equation. Then the third root is
x
3
,
namely, the
x
-coordinate of the sum
P
1
+
P
2
, and the polynomial factors as:
x
3
m
2
x
2
t
2
−
+
(
a
−
2
mt
)
x
+
(
b
−
)
=
(
x
−
x
1
)(
x
−
x
2
)(
x
−
x
3
).
In particular, the coefficient of the term of degree 2 is the same in both polynomials
and hence
m
2
m
2
x
2
as
stated in the theorem. To complete the proof we have to show that the
y
-coordinate
of
P
1
+
=
x
1
+
x
2
+
x
3
, from which it follows that
x
3
=
−
x
1
−
P
2
, namely
y
3
, also takes the value given in the statement of the theorem.
This coordinate is the opposite of the
y
-coordinate corresponding to
x
3
in the line
L
P
1
P
2
, obtained by substituting
x
3
for
x
in the equation of this line, so we have that
y
3
=−
(
m
(
x
3
−
x
1
)
+
y
1
)
=
m
(
x
1
−
x
3
)
−
y
1
, which completes the proof.
The important properties of the above-defined addition on
E
(
K
)
are summarized
in the following result:
(
K
)
Theorem 11.2
If E is an elliptic curve, then the addition of points gives E
the
structure of an abelian group.
It is clear that
O
is an identity element for this operation and also that the additive
inverse of
P
∈
E
(
K
)
is its
x
-axis reflection
−
P
. Moreover, it is also clear that the
operation is commutative, i.e.,
P
1
+
P
2
=
P
2
+
P
1
for all
P
1
,
P
2
∈
E
(
K
)
.Toshow
that we have a group it only remains to prove associativity, i.e., that
(
P
1
+
P
2
)
+
P
3
=
. The elementary way to prove associativity
is by direct calculation with the formulas given in Theorem 11.1. This calculation
is straightforward but extremely tedious because there are many cases to consider,
depending on whether or not
P
1
=
P
1
+
(
P
2
+
P
3
)
for all
P
1
,
P
2
,
P
3
∈
E
(
K
)
P
2
and so on. On
the other hand, this proof offers no additional insights so we do not include it here and
leave it as an exercise for the sufficiently patient reader. There are other, more enlight-
ening, proofs such as a geometrical one based on Bezout's theorem on intersections
of curves [182] or an algebraic one based on the theory of divisors on curves [181].
Recall that the order of an element
a
P
2
and whether or not
P
3
=
P
1
+
∈
G
, where
G
is an additive group, is the
smallest positive integer
n
such that
na
0 (if no such
n
exists then
a
has infinite
order). It can be shown by using the
Lutz-Nagell theorem
4
[181 (Corollary 7.2), 197
(Theorem 8.7)] that the rational curve
y
2
=
x
3
=
−
4
x
+
1 of Example 11.2 has no
.
5
However, there are rational elliptic curves with
O
points of finite order other than
=
O
points
of finite order and, of course, all the points of an elliptic curve over a
finite field
F
have this property because in this case the group
E
(
F
)
, being a subset
2
of
F
, is finite and hence so is the order of any point.
The smallest possible order of a point
P
∪{
O
}
=
O
is 2 and such a point has order
2 precisely when
P
=−
P
. Then
P
=
(
x
,
y
)
=
(
x
,
−
y
)
and hence
y
=
0 (recall
4
This theorem says that if
P
=
O
is a point of finite order of
E
(
Q
)
then it has integral coordinates
x
,
y
and, moreover, if
y
=
0then
y
2
divides 4
a
3
+
27
b
2
.
5
This produces a little terminological paradox: the only point of finite order in this curve is the
point at infinity!
