Cryptography Reference
In-Depth Information
addition and subtraction are much faster than multiplication, we do not con-
sider them in our analysis.
Similarly, multiplication by a constant is not
included.
2.6.2
Jacobian Coordinates
A modification of projective coordinates leads to a faster doubling proce-
dure. Let ( x : y : z ) represent the a ne point ( x/z 2 ,y/z 3 ). This is somewhat
natural since, as we'll see in Chapter 11, the function x has a double pole at
. The elliptic curve y 2 = x 3 + Ax + B
and the function y has a triple pole at
becomes
y 2 = x 3 + Axz 4 + Bz 6 .
The point at infinity now has the coordinates
=(1:1:0).
Let P i =( x i : y i : z i ), i =1 , 2, be points on the elliptic curve y 2
=
x 3 + Axz 4 + Bz 6 .Then
( x 1 : y 1 : z 1 )+( x 2 : y 2 : z 2 )=( x 3 : y 3 : z 3 ) ,
where x 3 ,y 3 ,z 3 are computed as follows: When P 1
=
±
P 2 ,
r = x 1 z 2 ,
s = x 2 z 1 ,
t = y 1 z 2 ,
u = y 2 z 1 ,
v = s
r,
w = u
t,
v 3
2 rv 2 + w 2 ,
tv 3 +( rv 2
x 3 =
3 =
x 3 ) w,
z 3 = vz 1 z 2 .
When P 1 = P 2 ,
v =4 x 1 y 1 ,
w =3 x 1 + Az 1 ,
x 3 = 2 v + w 2 ,
3 = 8 y 1 +( v − x 3 ) w,
z 3 =2 y 1 z 1 .
When P 1 = −P 2 ,wehave P 1 + P 2 = .
Addition of points takes 12 multiplications and 4 squarings. Doubling takes
3 multiplications and 6 squarings. There are no inversions.
When A = 3, a further speed-up is possible in doubling: we have w =
3( x 1 − z 1 )=3( x 1 + z 1 )( x 1 − z 1 ), which can be computed in one squaring and
one multiplication, rather than in 3 squarings. Therefore, doubling takes only
4 multiplications and 4 squarings in this case. The elliptic curves in NIST's
list of curves over fields F p ([86], [48, p. 262]) have A = 3 for this reason.
There are also situations where a point in one coordinate system can be
eciently added to a point in another coordinate system. For example, it takes
only 8 multiplications and 3 squarings to add a point in Jacobian coordinates
to one in ane coordinates. For much more on other choices for coordinates
and on ecient point addition, see [48, Sections 3.2, 3.3] and [27, Sections
13.2, 13.3].
Search WWH ::




Custom Search