Cryptography Reference
In-Depth Information
R
P
2
P
1
S
Figure 7.1 Chord and tangent rule for elliptic curve addition.
P
2
then let the line be the tangent to the curve at
P
1
). Denote by
R
the third point
7
of
intersection (counted according to multiplicities) of the line with the curve
E
.Nowdraw
the line
v
(
x
)
P
1
=
=
O
E
then this is the “line at infinity” and if
R
is an affine point this is a vertical line so a function of
x
only). Denote by
S
the third point
of intersection of this line with the curve
E
. Then one defines
P
1
+
=
0 between
O
E
and
R
(if
R
P
2
to be
S
.Overthe
real numbers this operation is illustrated in Figure
7.1
.
We now transform the above geometric description into algebra, and show that the
points
R
and
S
do exist. The first step is to write down the equation of the line between
P
1
=
(
x
2
,y
2
). We state the equation of the line as a definition and then
show that it corresponds to a function with the correct divisor.
(
x
1
,y
1
) and
P
2
=
Definition 7.9.1
Let
E
(
x,y
) be a Weierstrass equation for an elliptic curve over
k
.Let
2
.If
P
1
=
P
1
=
(
x
1
,y
1
)
,P
2
=
(
x
2
,y
2
)
∈
E
(
k
)
∩ A
ι
(
P
2
) then the line between
P
1
and
P
2
is
8
v
(
x
)
=
x
−
x
1
.
(3
x
1
+
If
P
1
=
ι
(
P
2
) then there are two subcases. If
P
1
=
P
2
then define
λ
=
2
a
2
x
1
+
a
4
)
/
(2
y
1
+
a
1
x
1
+
a
3
) and if
P
1
=
P
2
then define
λ
=
(
y
2
−
y
1
)
/
(
x
2
−
x
1
). The line
between
P
1
and
P
2
is then
l
(
x,y
)
=
y
−
λ
(
x
−
x
1
)
−
y
1
.
We stress that whenever we write
l
(
x,y
) then we are implicitly assuming that it is not a
vertical line
v
(
x
).
Warning:
Do not confuse the line
v
(
x
) with the valuation
v
P
. The notation
v
(
P
) means
the line evaluated at the point
P
. The notation
v
P
(
x
) means the valuation of the function
x
at the point
P
.
Exercise 7.9.2
Let the notation be as in Definition
7.9.1
. Show that if
P
1
=
ι
(
P
2
) then
v
(
P
1
)
=
v
(
P
2
)
=
0 and if
P
1
=
ι
(
P
2
) then
l
(
P
1
)
=
l
(
P
2
)
=
0.
7
Possibly this point is at infinity.
8
This includes the case
P
1
=
P
2
=
ι
(
P
1
).