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

Projective 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

Projective coordinates [database entry] represent x y as X Y Z satisfying the following equations:

  x=X/Z
  y=Y/Z

Best operation counts

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

12M for addition: 12M. 12M. 12M.
12M for addition with X2=1: 12M. 12M. 12M.
10M for addition with Z2=1: 10M.
8M for addition with Z1=1 and Z2=1: 8M.
12M for readdition: 12M after 12M. 12M after 12M. 12M after 12M. 6M+6S after 6M+12S. 9M+3S after 12M+6S.
11M for readdition with X2=1: 5M+6S after 5M+9S.
10M for readdition with Z2=1: 10M after 10M.
7M for readdition with Z1=1 and Z2=1: 7M after 8M.
8M for doubling: 7M+1S. 7M+1S.
6M for doubling with Z1=1: 3M+3S.
14M for tripling: 8M+6S.
102M for scaling: 1I+2M.

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

12M for addition: 12M. 12M. 12M.
12M for addition with X2=1: 12M. 12M. 12M.
10M for addition with Z2=1: 10M.
8M for addition with Z1=1 and Z2=1: 8M.
10.8M for readdition: 6M+6S after 6M+12S.
10M for readdition with Z2=1: 10M after 10M.
9.8M for readdition with X2=1: 5M+6S after 5M+9S.
7M for readdition with Z1=1 and Z2=1: 7M after 8M.
7.8M for doubling: 3M+6S. 3M+6S. 7M+1S. 7M+1S.
5.4M for doubling with Z1=1: 3M+3S.
12.8M for tripling: 8M+6S.
102M for scaling: 1I+2M.

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

12M for addition: 12M. 12M. 12M.
11.03M for addition with X2=1: 5M+9S.
10M for addition with Z2=1: 10M.
8M for addition with Z1=1 and Z2=1: 8M.
10.02M for readdition: 6M+6S after 6M+12S.
10M for readdition with Z2=1: 10M after 10M.
9.02M for readdition with X2=1: 5M+6S after 5M+9S.
7M for readdition with Z1=1 and Z2=1: 7M after 8M.
7.02M for doubling: 3M+6S. 3M+6S.
5.01M for doubling with Z1=1: 3M+3S.
12.02M for tripling: 8M+6S.
102M for scaling: 1I+2M.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	8M	7M
addition	Z2=1	10M	10M
addition		12M	12M
addition		12M	12M
addition		12M	12M
addition	X2=1	5M + 9S	5M + 6S
addition		6M + 12S	6M + 6S
addition		12M + 6S	9M + 3S
doubling	Z1=1	3M + 3S
doubling		7M + 1S
doubling		7M + 1S
doubling		3M + 6S
doubling		3M + 6S
doubling		6M + 3S
doubling		12M
doubling		3M + 6^³
tripling	3bd=1	8M + 6S + 1*b
tripling	a=3*d	11M + 4S + 2*a
tripling		10M + 1S + 29^³ + 2*d
scaling		1I + 2M

Explicit formulas for addition

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

Assumptions: Z1=1 and Z2=1.
Cost: 8M + 3add.
Cost: 7M + 3add dependent upon the first point.

Explicit formulas:

      X1Y2 = X1*Y2
      Y1X2 = Y1*X2
      X3 = Y1X2*Y1-Y2*X1Y2
      Y3 = X1*X1Y2-Y1X2*X2
      Z3 = Y2*X2-X1*Y1

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

Assumptions: Z2=1.
Cost: 10M + 3add.

Explicit formulas:

      X1Y2 = X1*Y2
      Y1X2 = Y1*X2
      Z1X2 = Z1*X2
      Z1Y2 = Z1*Y2
      X3 = Y1X2*Y1-Z1Y2*X1Y2
      Y3 = X1*X1Y2-Y1X2*Z1X2
      Z3 = Z1Y2*Z1X2-X1*Y1

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

Cost: 12M + 3add.
Source: 2001 Joye–Quisquater "Hessian elliptic curves and side-channel attacks".

Explicit formulas:

      T1 = X1
      T2 = Y1
      T3 = Z1
      T4 = X2
      T5 = Y2
      T6 = Z2
      T7 = T1*T6
      T1 = T1*T5
      T5 = T3*T5
      T3 = T3*T4
      T4 = T2*T4
      T2 = T2*T6
      T6 = T2*T7
      T2 = T2*T4
      T4 = T3*T4
      T3 = T3*T5
      T5 = T1*T5
      T1 = T1*T7
      T1 = T1-T4
      T2 = T2-T5
      T3 = T3-T6
      X3 = T2
      Y3 = T1
      Z3 = T3

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

Cost: 12M + 3add.
Source: 2009 Bernstein–Kohel–Lange (introduction).
Strongly unified.

Explicit formulas:

      Y1X2 = Y1*X2
      Y1Y2 = Y1*Y2
      Z1Y2 = Z1*Y2
      Z1Z2 = Z1*Z2
      X1Z2 = X1*Z2
      X1X2 = X1*X2
      X3 = Z1Z2*Z1Y2-X1X2*Y1X2
      Y3 = Y1Y2*Y1X2-Z1Z2*X1Z2
      Z3 = X1X2*X1Z2-Y1Y2*Z1Y2

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

Cost: 12M + 3add.

Explicit formulas:

      X1Y2 = X1*Y2
      X1Z2 = X1*Z2
      Y1Z2 = Y1*Z2
      Y1X2 = Y1*X2
      Z1X2 = Z1*X2
      Z1Y2 = Z1*Y2
      X3 = Y1X2*Y1Z2-Z1Y2*X1Y2
      Y3 = X1Z2*X1Y2-Y1X2*Z1X2
      Z3 = Z1Y2*Z1X2-X1Z2*Y1Z2

The "xmadd-2007-hcd" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: X2=1.
Cost: 5M + 9S + 15add + 2*2.
Cost: 5M + 6S + 12add dependent upon the first point.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      S0 = Y2^²
      S1 = Z2^²
      S2 = (Y2+Z2)^²-S0-S1
      S3 = 2*Y2
      S4 = 2*Z2
      R0 = X1^²
      R1 = Y1^²
      R2 = Z1^²
      R3 = X1+Y1
      Y3 = Y1+Z1
      Y3 = Y3^²
      Z3 = X1+Z1
      Z3 = Z3^²
      X3 = R3^²
      R3 = Y3-R1
      R3 = R3-R2
      Y3 = R0*S2
      Y3 = Y3-R3
      R3 = X3-R0
      R3 = R3-R1
      Z3 = Z3-R0
      Z3 = Z3-R2
      X3 = R1*S4
      R0 = Z3*S0
      X3 = X3-R0
      Z3 = R2*S3
      R0 = R3*S1
      Z3 = Z3-R0

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

Cost: 6M + 12S + 21add.
Cost: 6M + 6S + 12add dependent upon the first point.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 10, top.

Explicit formulas:

      XX1 = X1^²
      YY1 = Y1^²
      ZZ1 = Z1^²
      XY1 = (X1+Y1)^²-XX1-YY1
      XZ1 = (X1+Z1)^²-XX1-ZZ1
      YZ1 = (Y1+Z1)^²-YY1-ZZ1
      XX2 = X2^²
      YY2 = Y2^²
      ZZ2 = Z2^²
      XY2 = (X2+Y2)^²-XX2-YY2
      XZ2 = (X2+Z2)^²-XX2-ZZ2
      YZ2 = (Y2+Z2)^²-YY2-ZZ2
      X3 = YY1*XZ2-XZ1*YY2
      Y3 = XX1*YZ2-YZ1*XX2
      Z3 = ZZ1*XY2-XY1*ZZ2

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

Cost: 12M + 6S + 3add.
Cost: 9M + 3S + 3add dependent upon the first point.

Explicit formulas:

      X3 = Y1^²*Z2*X2-Y2^²*Z1*X1
      Y3 = X1^²*Y2*Z2-X2^²*Y1*Z1
      Z3 = Z1^²*X2*Y2-Z2^²*X1*Y1

Explicit formulas for doubling

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

Assumptions: Z1=1.
Cost: 3M + 3S + 11add + 3*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      A = X1^²
      B = Y1^²
      D = A+B
      G = (X1+Y1)^²-D
      X3 = (2*Y1-G)*(X1+A+1)
      Y3 = (G-2*X1)*(Y1+B+1)
      Z3 = (X1-Y1)*(G+2*D)

The "dbl-2007-hcd-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 7M + 1S + 8add.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      R0 = X1^²
      R1 = X1+Y1
      R1 = Y1*R1
      R2 = Z1+X1
      R2 = Z1*R2
      R2 = R0+R2
      R1 = R0+R1
      R0 = X1-Y1
      R0 = R1*R0
      Z3 = R0*Z1
      R1 = Z1-X1
      R1 = R2*R1
      X3 = R1*Y1
      R2 = -(R0+R1)
      Y3 = R2*X1

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

Cost: 7M + 1S + 8add.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      A = X1^²
      B = Y1*(X1+Y1)
      C = A+B
      D = Z1*(Z1+X1)
      E = A+D
      F = C*(X1-Y1)
      G = E*(Z1-X1)
      Z3 = F*Z1
      Y3 = -(F+G)*X1
      X3 = G*Y1

The "dbl-2007-hcd-3" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 3M + 6S + 15add + 3*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      A = X1^²
      B = Y1^²
      C = Z1^²
      D = A+B
      E = A+C
      F = B+C
      G = (X1+Y1)^²-D
      H = (X1+Z1)^²-E
      J = (Y1+Z1)^²-F
      X3 = (J-G)*(H+2*E)
      Y3 = (G-H)*(J+2*F)
      Z3 = (H-J)*(G+2*D)

The "dbl-2007-hcd-4" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 3M + 6S + 15add + 3*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      R0 = X1^²
      R1 = Y1^²
      R2 = Z1^²
      R3 = R0+R1
      R4 = R0+R2
      R5 = R1+R2
      R0 = X1+Y1
      R0 = R0^²
      R0 = R0-R3
      R1 = X1+Z1
      R1 = R1^²
      R1 = R1-R4
      R2 = Y1+Z1
      R3 = 2*R3
      R2 = R2^²
      R4 = 2*R4
      R2 = R2-R5
      R5 = 2*R5
      X3 = R2-R0
      R4 = R1+R4
      X3 = X3*R4
      Y3 = R0-R1
      R5 = R2+R5
      Y3 = Y3*R5
      Z3 = R1-R2
      R0 = R0+R3
      Z3 = Z3*R0

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

Cost: 6M + 3S + 3add.

Explicit formulas:

      XX = X1^²
      XXX = X1*XX
      YY = Y1^²
      YYY = Y1*YY
      ZZ = Z1^²
      ZZZ = Z1*ZZ
      X3 = Y1*(ZZZ-XXX)
      Y3 = X1*(YYY-ZZZ)
      Z3 = Z1*(XXX-YYY)

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

Cost: 12M + 3add.
Source: 2001 Joye–Quisquater "Hessian elliptic curves and side-channel attacks", applying the addition formulas to permuted input coordinates.

Explicit formulas:

      T1 = Z1
      T2 = X1
      T3 = Y1
      T4 = Y1
      T5 = Z1
      T6 = X1
      T7 = T1*T6
      T1 = T1*T5
      T5 = T3*T5
      T3 = T3*T4
      T4 = T2*T4
      T2 = T2*T6
      T6 = T2*T7
      T2 = T2*T4
      T4 = T3*T4
      T3 = T3*T5
      T5 = T1*T5
      T1 = T1*T7
      T1 = T1-T4
      T2 = T2-T5
      T3 = T3-T6
      X3 = T2
      Y3 = T1
      Z3 = T3

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

Cost: 3M + 6^³ + 3add.

Explicit formulas:

      X3 = Y1*(Z1^³-X1^³)
      Y3 = X1*(Y1^³-Z1^³)
      Z3 = Z1*(X1^³-Y1^³)

Explicit formulas for tripling

The "tpl-2007-hcd-3" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: 3*b*d=1.
Cost: 8M + 6S + 1*b + 12add + 2*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      R0 = X1^²
      X3 = R0*X1
      R0 = Y1^²
      Y3 = R0*Y1
      R0 = Z1^²
      Z3 = R0*Z1
      R0 = X3-Y3
      R0 = R0^²
      R1 = X3-Z3
      R1 = R1^²
      R2 = Y3-Z3
      R2 = R2^²
      Z3 = Z3+X3
      Z3 = Z3+Y3
      Z3 = b*Z3
      R3 = R0+R2
      R0 = R0+R1
      R4 = R1+R3
      Z3 = Z3*R4
      R4 = R1-R3
      R4 = R4*X3
      R3 = R2-R0
      R3 = Y3*R3
      X3 = X3*R2
      X3 = 2*X3
      X3 = X3-R3
      Y3 = Y3*R1
      Y3 = 2*Y3
      Y3 = Y3-R4

The "tpl-2007-hcd-2" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: a=3*d.
Cost: 11M + 4S + 2*a + 8add.
Source: 2007 Hisil–Carter–Dawson, plus elimination of common subexpressions.

Explicit formulas:

      XX = X1^²
      A = XX*X1
      YY = Y1^²
      B = YY*Y1
      ZZ = Z1^²
      C = ZZ*Z1
      AB = A-B
      BC = B-C
      CA = C-A
      U = B*CA
      V = A*BC
      X3 = a*(U*AB-V*BC)
      Y3 = a*(V*AB-U*CA)
      Z3 = (A+B+C)*(BC*CA-AB^²)

The "tpl-2007-hcd" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 10M + 1S + 29^³ + 2*d + 16add + 2*3.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

      X3 = 3*d*(Y1^³*(Z1^³-X1^³)*(X1^³-Y1^³)-X1^³*(Y1^³-Z1^³)*(Y1^³-Z1^³))
      Y3 = 3*d*(X1^³*(Y1^³-Z1^³)*(X1^³-Y1^³)-Y1^³*(Z1^³-X1^³)*(Z1^³-X1^³))
      Z3 = (X1^³+Y1^³+Z1^³)*((Y1^³-Z1^³)*(Z1^³-X1^³)-(X1^³-Y1^³)^²)

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 + 2M + 0add.

Explicit formulas:

      A = 1/Z1
      X3 = A*X1
      Y3 = A*Y1
      Z3 = 1