# Binary Curve Jacobian Coordinates

## Introduction

'Jacobian Coordinates' are used to represent elliptic curve points on
binary curves y^2 + xy = x^3 + ax^2 + b. They give a speed benefit
over

Affine
Coordinates when the cost for field inversions is significantly
higher than field multiplications. In ''Jacobian Coordinates'' the
triple (X, Y, Z) represents the affine point (X / Z^2, Y / Z^3).

## Point Doubling (5M + 5S)

Let (X, Y, Z) be a point (unequal to the 'point at infinity')
represented in 'Jacobian Coordinates'. Then its double (X', Y', Z')
can be calculated by

Precomputation: compute d6 = sqrt(sqrt(b)) = b^(2^(m - 2)) (if the underlying field is GF(2^m))
if (X == 0)
return POINT_AT_INFINITY
Z' = X*Z^2
X' = (X + d6*Z^2)^4
l = Z' + X^2 + Y*Z
Y' = X^4*Z' + l*X'
return (X', Y', Z')

Note: For 'Koblitz Curves', where b = 1, the multiplication with d6
can be omitted. Doubling costs therefore reduce to 4M + 5S.

## Point Addition (15M + 5S or 14M + 4S)

Let (X1, Y1, Z1) and (X2, Y2, Z2) be two points (both unequal to the
'point at infinity') represented in 'Jacobian Coordinates'. Then
the sum (X3, Y3, Z3) can be calculated by

U1 = X1*Z2^2
U2 = X2*Z1^2
S1 = Y1*Z2^3
S2 = Y2*Z1^3
if (U1 == U2)
if (S1 != S2)
return POINT_AT_INFINITY
else
return POINT_DOUBLE(X1, Y1, Z1)
W = U1 + U2
R = S1 + S2
L = Z1*W
Z3 = L*Z2
V = R*X2 + L*Y2
T = R + Z3
X3 = a*Z3^2 + T*R + W^3
Y3 = T*X3 + V*L^2
return (X3, Y3, Z3)

Note: if the value of a is small (say 0 or 1), the multiplication with
a can be replaced by simpler operations and the overall multiplication
count is reduced to 14. For a = 0 the squaring of Z3 can be omitted,
too.

## Mixed Addition (with affine point) (11M + 4S or 10M + 3S)

Let (X1, Y1, Z1) be a point represented in 'Jacobian Coordinates' and
(X2, Y2) a point in

Affine Coordinates
(both unequal to the 'point at infinity'). A formula to add those
points can be readily derived from the regular jacobian point addition
by replacing each occurance of "Z2" by "1" (and
thereby dropping four field multiplications and one field squaring).