Cryptography Reference
In-Depth Information
then
P
i
=(
s
i
,t
i
)
with
s
i
=1
/y
i
,
i
=
x
i
/y
i
.
The points
P
1
,P
2
,P
3
lie on the line
at
+
b
+
ds
=0.
Since
P
1
,P
2
∈ E
r
, Lemma 8.3 implies that
p
3
r
r
|
s
i
,
|
t
i
,
for
i
=1
,
2
.
As discussed in Section 2.4, at a finite point (
x, y
), the order of intersection
of the line
ax
+
by
+
d
= 0 and the curve
y
2
=
x
3
+
Ax
+
B
can be calculated by
using projective coordinates and considering the line
aX
+
bY
+
dZ
=0and
the curve
ZY
2
=
X
3
+
AXZ
2
+
BZ
3
. In this case,
x
=
X/Z
and
y
=
Y/Z
.
If we start with a line
at
+
b
+
ds
= 0 and the curve
s
=
t
3
+
Ats
2
+
Bs
3
,
we can homogenize to get
aT
+
bU
+
dS
= 0 and
SU
2
=
T
3
+
AT S
2
+
BS
3
.
In this case, we have
t
=
T/U
and
s
=
S/U
.Ifwelet
Z
=
S
,
Y
=
U
,
X
=
T
,
we find that we are working with the same line and curve as above. A point
(
x, y
) corresponds to
t
=
T/U
=
X/Y
=
x/y
and
s
=
S/U
=
Z/Y
=1
/y.
Since orders of intersection can be calculated using the projective models, it
follows that the order of intersection of the line
ax
+
by
+
d
= 0 with the curve
y
2
=
x
3
+
Ax
+
B
at (
x, y
) is the same as the order of intersection of the line
at
+
b
+
ds
= 0 with the curve
s
=
t
3
+
Ats
2
+
Bs
3
at (
s, t
)=(1
/y, x/y
).
For example, the line and curve are tangent in the variables
x, y
if and only if
they are tangent in the variables
t, s
. This allows us to do the elliptic curve
group calculations using
t, s
instead of
x, y
.
LEMMA 8.4
A ine
t
=
c
,where
c ∈
Q
isaconstant w ith
c ≡
0(mod
p
)
,intersectsthe
curve
s
=
t
3
+
As
2
t
+
Bs
3
in atmostonepoint
(
s, t
)
with
s ≡
0(mod
p
)
.
Thisline isnottangent at such a pointofintersection.
PROOF
Suppose we have two values of
s
,callthem
s
1
,s
2
with
s
1
≡ s
2
≡
0
(mod
p
). Suppose
s
1
≡
s
2
(mod
p
k
)forsome
k
1. Write
s
i
=
ps
i
.Then
≥
s
1
≡ s
2
(mod
p
k−
1
), so
s
1
2
≡ s
2
2
(mod
p
k−
1
), so
s
1
=
p
2
s
1
2
≡ p
2
s
2
2
=
s
2
(mod
p
k
+1
). Similarly,
s
1
≡ s
2
(mod
p
k
+2
). Therefore,
s
1
=
c
3
+
Acs
1
+
Bs
1
≡
c
3
+
Acs
2
+
Bs
2
=
s
2
(mod
p
k
+1
)
.
By induction, we have
s
1
≡ s
2
(mod
p
k
) for all
k
. It follows that
s
1
=
s
2
,so
there is at most one point of intersection with
s ≡
0(mod
p
).
Search WWH ::
Custom Search