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).