Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Hessian curves EFD / Genus-1 large-characteristic / Extended coordinates for Hessian curves

Extended coordinates for Hessian curves

An elliptic curve in Hessian form [more information] has parameters d and coordinates x y satisfying the following equations:

  x^³+y^³+1=3*d*x*y

Extended coordinates [database entry] represent x y as X Y Z XX YY ZZ XY YZ XZ satisfying the following equations:

  x=X/Z
  y=Y/Z
  XX=X*X
  YY=Y*Y
  ZZ=Z*Z
  XY=2*X*Y
  XZ=2*X*Z
  YZ=2*Y*Z

Best operation counts

Smallest multiplication counts assuming I=100M, S=1M, *param=0M, add=0M, *const=0M:

12M for addition: 6M+6S.
11M for addition with Z2=1: 5M+6S.
12M for readdition: 6M+6S after 6M+6S.
11M for readdition with Z2=1: 5M+6S after 5M+6S.
9M for doubling: 3M+6S. 3M+6S.
105M for scaling: 1I+3M+2S.

Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:

10.8M for addition: 6M+6S.
9.8M for addition with Z2=1: 5M+6S.
10.8M for readdition: 6M+6S after 6M+6S.
9.8M for readdition with Z2=1: 5M+6S after 5M+6S.
7.8M for doubling: 3M+6S. 3M+6S.
104.6M for scaling: 1I+3M+2S.

Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:

10.02M for addition: 6M+6S.
9.02M for addition with Z2=1: 5M+6S.
10.02M for readdition: 6M+6S after 6M+6S.
9.02M for readdition with Z2=1: 5M+6S after 5M+6S.
7.02M for doubling: 3M+6S. 3M+6S.
104.34M for scaling: 1I+3M+2S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z2=1	5M + 6S	5M + 6S
addition		6M + 6S	6M + 6S
doubling		3M + 6S
doubling		3M + 6S
scaling		1I + 3M + 2S

Explicit formulas for addition

The "madd-20080225-hwcd" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z2=1.
Cost: 5M + 6S + 12add.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 10, top.

Explicit formulas:

      X3 = YY1*XZ2-XZ1*YY2
      Y3 = XX1*YZ2-YZ1*XX2
      Z3 = ZZ1*XY2-XY1
      XX3 = X3^²
      YY3 = Y3^²
      ZZ3 = Z3^²
      XY3 = (X3+Y3)^²-XX3-YY3
      XZ3 = (X3+Z3)^²-XX3-ZZ3
      YZ3 = (Y3+Z3)^²-YY3-ZZ3

The "add-20080225-hwcd" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 6M + 6S + 12add.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 10, top.

Explicit formulas:

      X3 = YY1*XZ2-XZ1*YY2
      Y3 = XX1*YZ2-YZ1*XX2
      Z3 = ZZ1*XY2-XY1*ZZ2
      XX3 = X3^²
      YY3 = Y3^²
      ZZ3 = Z3^²
      XY3 = (X3+Y3)^²-XX3-YY3
      XZ3 = (X3+Z3)^²-XX3-ZZ3
      YZ3 = (Y3+Z3)^²-YY3-ZZ3

Explicit formulas for doubling

The "dbl-20080225-hwcd" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 3M + 6S + 18add + 3*2.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 10, bottom.

Explicit formulas:

      X3 = (XY1-YZ1)*(XZ1+2*(XX1+ZZ1))
      Y3 = (XZ1-XY1)*(YZ1+2*(YY1+ZZ1))
      Z3 = (YZ1-XZ1)*(XY1+2*(XX1+YY1))
      XX3 = X3^²
      YY3 = Y3^²
      ZZ3 = Z3^²
      XY3 = (X3+Y3)^²-XX3-YY3
      XZ3 = (X3+Z3)^²-XX3-ZZ3
      YZ3 = (Y3+Z3)^²-YY3-ZZ3

The "mdbl-20080225-hwcd" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 3M + 6S + 18add + 3*2.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 10, bottom.

Explicit formulas:

      X3 = (XY1-YZ1)*(XZ1+2*(XX1+ZZ1))
      Y3 = (XZ1-XY1)*(YZ1+2*(YY1+ZZ1))
      Z3 = (YZ1-XZ1)*(XY1+2*(XX1+YY1))
      XX3 = X3^²
      YY3 = Y3^²
      ZZ3 = Z3^²
      XY3 = (X3+Y3)^²-XX3-YY3
      XZ3 = (X3+Z3)^²-XX3-ZZ3
      YZ3 = (Y3+Z3)^²-YY3-ZZ3

Explicit formulas for tripling

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

Explicit formulas for scaling

The "z" scaling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 1I + 3M + 2S + 0add + 2*2.

Explicit formulas:

      A = 1/Z1
      X3 = A*X1
      Y3 = A*Y1
      Z3 = 1
      XX3 = X3^²
      YY3 = Y3^²
      ZZ3 = 1
      XZ3 = 2*X3
      YZ3 = 2*Y3
      XY3 = XZ3*Y3