Binary Curve López-Dahab Coordinates

Introduction

'López-Dahab Coordinates' (short: LD coordinates) are used to represent elliptic curve points on binary curves y^2 + xy = x^3 + ax^2 + b. In 'López-Dahab Coordinates' the triple (X, Y, Z) represents the affine point (X / Z, Y / Z^2).

Point Doubling (up to 5M)

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

 if (X == 0)
   return POINT_AT_INFINITY
 else
   A = X^2
   B = Z^2
   Z' = A*B
   C = A^2
   D = b*B^2
   X' = C + D
   Y' = D*Z' + X'*(a*Z' + Y^2 + D)
   return (X', Y', Z')

Note that the total number of field multiplications can be reduced if the curve coefficient a and b are carefully chosen.

Point Addition (up to 14M)

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

 A = X1*Z2 + X2*Z1
 B = Y1*Z2^2 + Y2*Z1^2
 if (A == 0)
   if (B != 0) 
     return POINT_AT_INFINITY
   else
     return POINT_DOUBLE(X1, Y1, Z1)
 C = Z1*A
 D = Z2*C
 Z3 = D^2
 X3 = D*(A^2 + B) + B^2 + a*Z3
 E = C*D
 F = E^2*Y2
 G = X3 + X2*E
 Y3 = Z3*X3 + F + B*D*G
 return (X3, Y3, Z3)

Note that if curve coefficient a is carefully chosen, the number of field multiplications can be reduced to 13M.