Prime Curve Modified Jacobian Coordinates

Introduction

'Modified Jacobian Coordinates' are used to represent elliptic curve points on prime curves y^2 = x^3 + ax + b. Their usage might give a speed benefit over regular Jacobian Coordinates only when a is neither equal to 0 nor to -3. In 'Modified Jacobian Coordinates' the quadruple (X, Y, Z, aZ^4) represents the affine point (X / Z^2, Y / Z^3). Therefore the first three positions coincide with those of regular 'Jacobian Coordinates'. For further details see the CiteSeer cache of Cohen, Miyaji, Ono: Efficient Elliptic Curve Exponentiation using Mixed Coordinates.

Point Doubling (4M + 4S)

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

 if (Y == 0) 
   return POINT_AT_INFINITY 
 else
   S = 4*X*Y^2
   U = 8*Y^4
   M = 3X^2 + (aZ^4)
   X' = M^2 - 2S
   Y' = M*(S - X') - U
   Z' = 2*Y*Z
   aZ'^4 = 2U*(aZ^4)
   return (X', Y', Z', aZ'^4)

Point Addition (13M + 6S)

Let (X1, Y1, Z1, aZ1^4) and (X2, Y2, Z2, aZ2^4) be two points (both unequal to the 'point at infinity') represented in 'Modified Jacobian Coordinates'. Then the sum (X3, Y3, Z3, aZ3^4) 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, aZ1^4)
 H = U2 - U1
 R = S2 - S1
 X3 = R^2 - H^3 - 2*U1*H^2
 Y3 = R*(U1*H^2 - X3) - S1*H^3
 Z3 = Z1*Z2*H
 aZ3^4 = a*Z3^4
 return (X3, Y3, Z3, aZ3^4)

Notice that this point addition routine is almost identical to that of the regular Jacobian point addition.

Mixed Addition (with affine point) (9M + 5S)

Let (X1, Y1, Z1, aZ1^4) be a point represented in 'Modified 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 modified jacobian point addition by replacing each occurance of "Z2" by "1" (and thereby dropping four field multiplications and one field squaring).

Mixed Addition (with chudnovsky point) (12M + 5S)

Let (X1, Y1, Z1, aZ1^4) be a point represented in 'Modified Jacobian Coordinates' and (X2, Y2, Z2, Z2^2, Z2^3) a point in Chudnovsky Coordinates (both unequal to the 'point at infinity'). Then the sum (X3, Y3, Z3, aZ3^4) can be readily calculated using the addition formula given above (saving one field multiplication and one field squaring).