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