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