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