Cryptography Reference
In-Depth Information
line at
P
,
L
PP
, which may be seen as the limit of the lines
L
PQ
as
Q
approaches
P
.
The intersection of the tangent with the curve has multiplicity at least 2 and, arguing
as above, we deduce that it intersects the curve at another point
R
, which could be
equal to
P
in case the intersection has multiplicity 3 (when this happens we say that
P
is an inflection point of
E
). If the tangent is a vertical line then we have
R
=
O
and if
P
=
O
then the tangent at
O
is the
line at infinity
which intersects the curve
at the point
O
with multiplicity three. Thus we regard
O
as an inflection point of the
curve and we have that
R
in this case.
As mentioned above, the idea to define the addition of points in the curve is to set
the sum of two points
P
,
Q
, to be the reflection of
R
in the
x
-axis, where
R
is the
third point of intersection of
L
PQ
with the curve. Note that this makes sense because
an elliptic curve is symmetric about the
x
axis, so that if the point
=
O
(
x
0
,
y
0
)
lies on the
curve, then the point
(
x
0
,
−
y
0
)
is also on the curve. We denote the reflection of
R
by
−
R
, where
R
is defined as above (this construction
is often called the
chord-tangent method
). The point at infinity is a special case and
we regard it as its own reflection about the
x
-axis. Then, if
P
R
and so we define
P
+
Q
=−
=
O
, what is the point
is the vertical line through
P
and the third point of
intersection with the curve is precisely
P
+
O
? The line joining
P
and
O
−
P
. The reflection of this point in the
x
-axis
is
P
so we obtain that
P
+
O
=
O
+
P
=
P
. Similarly,
O
+
O
=
O
because the
tangent at
O
is the line at infinity. Thus we see that
O
acts as an additive identity
(or zero element) for this operation. We also see that
P
+
(
−
P
)
=−
P
+
P
=
O
,
so that the point
P
is actually the opposite (or additive inverse, or negative) of
P
with respect to the addition we have defined. The opposite element in a group is also
sometimes called the symmetric so here we have that
P
and
−
−
P
are symmetric to
each other both in the geometric and the group-theoretic sense.
Example 11.2
Let us consider the previous curve of equation
y
2
x
3
=
−
4
x
+
1.
Suppose we want to compute the sumof the points
P
.
As we have seen in Example 11.1, the third point of intersection of
L
PQ
with the
curve is
R
=
(
−
1
,
2
)
and
Q
=
(
1
/
4
,
1
/
8
)
=
(
3
,
−
4
)
, so that
P
+
Q
=−
R
=
(
3
,
4
)
. We may use Maple to obtain
a graphic representation of this construction.
> with
∼
([plots, plottools]):
> F := yˆ2-xˆ3+4*x-1:
L := 2*y+3*x-1:
el := implicitplot([F, L, x-3], x = -2.3 .. 3.3, y = -4.5 .. 4.5,
resolution = 1000, crossingrefine = 20, gridrefine = 6, color = black):
pts := pointplot([[-1, 2], [1/4, 1/8], [3, -4], [3, 4]]):
txt := textplot([[-.8, 2.1, 'P'], [.4, .2, 'Q'], [3.2, -4, 'R'], [2.7, 4, 'P+Q']]):
The construction is then illustrated in the following drawing:
