Cryptography Reference
In-Depth Information
Lemma 7.9.3
Let P
1
=
(
x
1
,y
1
)
∈
E
(
k
)
and let P
2
=
ι
(
P
1
)
. Let v
(
x
)
=
(
x
−
x
1
)
as in
Definition
7.9.1
. Then
div(
v
(
x
))
=
(
P
1
)
+
(
P
2
)
−
2(
O
E
)
.
Let P
1
=
(
x
1
,y
1
)
,P
2
=
(
x
2
,y
2
)
∈
E
(
k
)
be such that P
1
=
ι
(
P
2
)
and let l
(
x,y
)
=
y
−
λ
(
x
−
x
1
)
−
y
1
be as in Definition
7.9.1
. Then there exists x
3
∈ k
such that E
(
x,λ
(
x
−
=−
i
=
1
(
x
x
1
)
+
y
1
)
−
x
i
)
and
div(
l
(
x,y
))
=
(
P
1
)
+
(
P
2
)
+
(
R
)
−
3(
O
E
)
where R
=
(
x
3
,λ
(
x
3
−
x
1
)
+
y
1
)
.
Proof
The first part is just a restatement of Lemma
7.7.10
.
For the second part set
G
(
x
)
=−
E
(
x,λ
(
x
−
x
1
)
+
y
1
), which is a monic polynomial
over
k
of degree 3. Certainly,
x
1
and
x
2
are roots of
G
(
x
) over
k
so if
x
1
=
x
2
then
G
(
x
)
has a third root
x
3
over
k
. In the case
x
1
=
x
2
we have
P
1
=
P
2
=
ι
(
P
2
). Make a linear
y
2
change of variables so that (
x
1
,y
1
)
=
(
x
2
,y
2
)
=
0. The curve equation is
E
(
x,y
)
=
+
(
x
3
a
2
x
2
a
1
xy
+
a
3
y
−
+
+
a
4
x
) and
a
3
=
0 since (0
,
0)
=
ι
(0
,
0). Now, by definition,
l
(
x,y
)
=
a
4
x/a
3
and one has
(
a
4
x/a
3
)
2
(
x
3
a
2
x
2
G
(
x
)
=
E
(
x,a
4
x/a
3
)
=
+
a
1
x
(
a
4
x/a
3
)
+
a
4
x
−
+
+
a
4
x
)
which is divisible by
x
2
. Hence,
G
(
x
) splits completely over
.
For the final part we consider
l
(
x,y
) as a function on the affine curve. By Lemma
7.4.14
and Lemma
7.4.16
we have
v
O
E
(
l
(
x,y
))
k
=
min
{
v
O
E
(
y
)
,v
O
E
(
x
)
,v
O
E
(1)
}=−
3. Since
deg(div(
l
(
x,
y
)))
=
0 there are three affine zeroes counted according to mu
l
tiplicity.
Define
l
(
x,y
)
=
y
+
(
a
1
x
+
a
3
)
+
λ
(
x
−
x
1
)
+
y
1
.
Note
that
l
=−
l
◦
ι
so
v
P
(
l
(
x,y
))
=
v
ι
(
P
)
(
l
(
x,y
)). One can check that
3
=−
−
+
=
−
l
(
x,y
)
l
(
x,y
)
E
(
x,λ
(
x
x
1
)
y
1
)
(
x
x
i
)
(7.9)
i
=
1
where the first equality is equivalence modulo
E
(
x,y
), not equality of polynomials. Hence,
for any point
P
∈
E
(
k
),
3
x
i
)
.
v
P
(
l
(
x,y
))
+
v
P
(
l
(
x,y
))
=
v
P
(
x
−
i
=
1
Write
P
i
=
(
x
i
,y
i
), let
e
i
be the multiplicity of
x
i
in the right-hand side of equation (
7.9
)
and reca
l
l that
v
P
i
(
x
−
=
1if
P
i
=
=
x
i
)
ι
(
P
i
) and 2 otherwise. Also
no
te that
l
(
P
i
)
0
implies
l
(
P
i
)
=
0 unless
P
i
=
ι
(
P
i
), in which case
v
P
i
(
l
(
x,y
))
=
v
P
i
(
l
(
x,y
)). It follows
that
v
P
i
(
l
(
x,y
))
=
e
i
, which proves the result.
Remark 7.9.4
It follows from the above results that it does make sense to speak of the
“third point of intersection”
R
of
l
(
x,y
) with
E
and to call
l
(
x,y
) a tangent line in the case
when
P
1
=
P
2
. Hence, we have justified the assumptions made in the informal description
of the chord-and-tangent rule.
Exercise 7.9.5
Let
E
(
x,y,z
) be a Weierstrass equation for an elliptic curve. The line
z
=
0
is called the line at infinity on
E
. Show that
z
=
0 only passes through (0
,
0) on the affine
curve given by the equation
E
(
x,
1
,z
)
=
0.
