Cryptography Reference
In-Depth Information
Completing the square yields
y
1
=
x
3
+2
x
2
−
5
x −
6
,
1
where
y
1
=
y
+1
−
2
x
.
2.6 Other Coordinate Systems
The formulas for adding two points on an elliptic curve in Weierstrass form
require 2 multiplications, 1 squaring, and 1 inversion in the field. Although
finding inverses is fast, it is much slower than multiplication. In [27, p. 282],
it is estimated that inversion takes between 9 and 40 times as long as multi-
plication. Moreover, squaring takes about 0.8 the time of multiplication. In
many situations, this distinction makes no difference. However, if a central
computer needs to verify many signatures in a second, such distinctions can
become relevant. Therefore, it is sometimes advantageous to avoid inversion
in the formulas for point addition. In this section, we discuss a few alternative
formulas where this can be done.
2.6.1
Projective Coordinates
A natural method is to write all the points as points (
x
:
y
:
z
) in projective
space. By clearing denominators in the standard formulas for addition, we
obtain the following:
Let
P
i
=(
x
i
:
y
i
:
z
i
),
i
=1
,
2, be points on the elliptic curve
y
2
z
=
x
3
+
Axz
2
+
Bz
3
.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
,
w
=
u
2
z
1
z
2
− v
3
−
2
v
2
x
1
z
2
,
u
=
y
2
z
1
− y
1
z
2
,
v
=
x
2
z
1
− x
1
z
2
,
y
3
=
u
(
v
2
x
1
z
2
−
v
3
y
1
z
2
,
3
=
v
3
z
1
z
2
.
x
3
=
vw,
w
)
−
When
P
1
=
P
2
,
t
=
Az
1
+3
x
1
,
w
=
t
2
u
=
y
1
z
1
,
v
=
ux
1
y
1
,
−
8
v,
8
y
1
u
2
,
3
=8
u
3
.
x
3
=2
uw,
y
3
=
t
(4
v
−
w
)
−
When
P
1
=
−P
2
,wehave
P
1
+
P
2
=
∞
.
Point addition takes 12 multiplications and 2 squarings, while point dou-
bling takes 7 multiplications and 5 squarings. No inversions are needed. Since
Search WWH ::
Custom Search