Last modified on 17 July 2014, at 08:58

Cryptography/Prime Curve/Chudnovsky Coordinates

<Cryptography

IntroductionEdit

Chudnovsky Coordinates are used to represent elliptic curve points on prime curves y^2 = x^3 + ax + b. They give a speed benefit over Affine Coordinates when the cost for field inversions is significantly higher than field multiplications. In Chudnovsky Coordinates the quintuple (X, Y, Z, Z^2, Z^3) represents the affine point (X / Z^2, Y / Z^3).

Point Doubling (5M + 6S or 5M + 4S)Edit

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

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

Note: if a = -3, then M can also be calculated as M = 3*(X + Z^2)*(X - Z^2), saving 2 field squarings.

Point Addition (11M + 3S)Edit

Let (X1, Y1, Z1, Z1^2, Z1^3) and (X2, Y2, Z2, Z2^2, Z2^3) be two points (both unequal to the point at infinity) represented in Chudnovsky Coordinates. Then the sum (X3, Y3, Z3, Z3^2, Z3^3) 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, Z1^2, Z1^3)
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 = H*Z1*Z2
Z3^2 = Z3^2
Z3^3 = Z3^2 * Z3
return (X3, Y3, Z3)

Mixed Addition (with affine point) (8M + 3S)Edit

Let (X1, Y1, Z1, Z1^2, Z1^3) be a point represented in Chudnovsky 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 chudnovsky point addition by replacing each occurrence of "Z2" by "1" (and thereby dropping three field multiplications).

Mixed Addition (with jacobian point) (11M + 3S)Edit

See Jacobian Coordinates for further details.