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

Projective coordinates for Edwards curves

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

  x^²+y^²=c^²*(1+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:

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

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

10.8M for addition: 10M+1S. 10M+1S. 10M+1S.
9.8M for addition with X2=1: 9M+1S.
9M for addition with Z2=1: 9M.
6.8M for addition with Z1=1 and Z2=1: 6M+1S.
10.6M for readdition: 9M+2S after 10M+3S.
9.8M for readdition with X2=1: 9M+1S after 9M+1S.
9M for readdition with Z2=1: 9M after 9M.
6.8M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
6.2M for doubling: 3M+4S. 3M+4S. 3M+4S.
5.4M for doubling with Z1=1: 3M+3S.
12.2M for tripling: 9M+4S. 9M+4S.
102M for scaling: 1I+2M.

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

10.35M for addition: 7M+5S.
9.67M for addition with X2=1: 9M+1S.
9M for addition with Z2=1: 9M.
6.67M for addition with Z1=1 and Z2=1: 6M+1S.
10.34M for readdition: 9M+2S after 10M+3S.
9.67M for readdition with X2=1: 9M+1S after 9M+1S.
9M for readdition with Z2=1: 9M after 9M.
6.67M for readdition with Z1=1 and Z2=1: 6M+1S after 6M+1S.
5.68M for doubling: 3M+4S. 3M+4S. 3M+4S.
5.01M for doubling with Z1=1: 3M+3S.
11.68M for tripling: 9M+4S. 9M+4S.
102M for scaling: 1I+2M.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	6M + 1S + 1c + 1d	6M + 1S + 1c + 1d
addition	k*c=1 and Z2=1	9M + 1*k	9M + 1*k
addition	X2=1	9M + 1S + 1c + 1d	9M + 1S + 1c + 1d
addition	Z2=1	9M + 1S + 1c + 1d	9M + 1S + 1c + 1d
addition	Z2=1	9M + 1S + 1c + 1d	9M + 1S + 1c + 1d
addition	c2=2*c and Z2=1	6M + 5S + 1c2 + 1d	6M + 5S + 1c2 + 1d
addition		10M + 1S + 1c + 1d	10M + 1S + 1c + 1d
addition		10M + 1S + 1c + 1d	10M + 1S + 1c + 1d
addition	i^²=-1	10M + 1S + 3i + 1c + 1*d	10M + 1S + 2i + 1c + 1*d
addition	k*c=1	11M + 1*k	11M + 1*k
addition	c2=2*c	7M + 5S + 1c2 + 1d	7M + 5S + 1c2 + 1d
addition	k*c=1	10M + 3S + 1*k	9M + 2S + 1*k
doubling	cc2=2cc and Z1=1	3M + 3S + 2*c
doubling		3M + 4S + 3*c
doubling		3M + 4S + 3*c
doubling		3M + 4S + 3*c
tripling	c2=2*c	9M + 4S + 1*c2
tripling		9M + 4S + 1*c
tripling	c=1	7M + 7S
tripling	cc4=4cc	7M + 7S + 1*cc4
scaling		1I + 2M

Explicit formulas for addition

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

Assumptions: Z1=1 and Z2=1.
Cost: 6M + 1S + 1*c + 1*d + 8add.
Cost: 6M + 1S + 1*c + 1*d + 7add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      C = X1*X2
      D = Y1*Y2
      E = d*C*D
      X3 = (1-E)*((X1+Y1)*(X2+Y2)-C-D)
      Y3 = (1+E)*(D-C)
      Z3 = c*(1-E^²)

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

Assumptions: k*c=1 and Z2=1.
Cost: 9M + 1*k + 8add.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 8.

Explicit formulas:

      A = X1
      B = Y1
      C = Z1*X2
      D = Z1*Y2
      E = A*B
      F = C*D
      G = E+F
      H = E-F
      J = (A-C)*(B+D)-H
      K = (A+D)*(B+C)-G
      X3 = G*J
      Y3 = H*K
      Z3 = k*J*K

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

Assumptions: X2=1.
Cost: 9M + 1S + 1*c + 1*d + 4add.
Source: 2007 Hisil–Carter–Dawson.
Strongly unified.

Explicit formulas:

      T0 = X1*Y2
      T0 = T0+Y1
      Y3 = Y1*Y2
      T1 = Y3*X1
      Y3 = Y3-X1
      Z3 = Z1*Z2
      X3 = T0*Z3
      Y3 = Y3*Z3
      T1 = d*T1
      Z3 = Z3^²
      T0 = Z3-T1
      Z3 = Z3+T1
      X3 = X3*T0
      Y3 = Y3*Z3
      Z3 = Z3*T0
      Z3 = c*Z3

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

Assumptions: Z2=1.
Cost: 9M + 1S + 1*c + 1*d + 7add.
Cost: 9M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      R1 = X1
      R2 = Y1
      R3 = Z1
      R4 = X2
      R5 = Y2
      R7 = R1+R2
      R6 = R4+R5
      R1 = R1*R4
      R2 = R2*R5
      R7 = R7*R6
      R7 = R7-R1
      R7 = R7-R2
      R7 = R7*R3
      R6 = R1*R2
      R6 = d*R6
      R2 = R2-R1
      R2 = R2*R3
      R3 = R3^²
      R1 = R3-R6
      R3 = R3+R6
      R2 = R2*R3
      R3 = R3*R1
      R1 = R1*R7
      R3 = c*R3
      X3 = R1
      Y3 = R2
      Z3 = R3

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

Assumptions: Z2=1.
Cost: 9M + 1S + 1*c + 1*d + 7add.
Cost: 9M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

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

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

Assumptions: c2=2*c and Z2=1.
Cost: 6M + 5S + 1*c2 + 1*d + 13add + 1*2.
Cost: 6M + 5S + 1*c2 + 1*d + 12add + 1*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      B = Z1^²
      C = X1*X2
      D = Y1*Y2
      E = d*C*D
      BB = B^²
      EE = E^²
      H = (Z1+B)^²-BB
      I = (Z1+E)^²-EE
      X3 = (H-I)*((X1+Y1)*(X2+Y2)-C-D)
      Y3 = (H+I-2*B)*(D-C)
      Z3 = c2*(BB-EE)

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

Cost: 10M + 1S + 1*c + 1*d + 7add.
Cost: 10M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      R1 = X1
      R2 = Y1
      R3 = Z1
      R4 = X2
      R5 = Y2
      R6 = Z2
      R3 = R3*R6
      R7 = R1+R2
      R8 = R4+R5
      R1 = R1*R4
      R2 = R2*R5
      R7 = R7*R8
      R7 = R7-R1
      R7 = R7-R2
      R7 = R7*R3
      R8 = R1*R2
      R8 = d*R8
      R2 = R2-R1
      R2 = R2*R3
      R3 = R3^²
      R1 = R3-R8
      R3 = R3+R8
      R2 = R2*R3
      R3 = R3*R1
      R1 = R1*R7
      R3 = c*R3
      X3 = R1
      Y3 = R2
      Z3 = R3

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

Cost: 10M + 1S + 1*c + 1*d + 7add.
Cost: 10M + 1S + 1*c + 1*d + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

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

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

Assumptions: i^²=-1.
Cost: 10M + 1S + 3*i + 1*c + 1*d + 9add + 2*2.
Cost: 10M + 1S + 2*i + 1*c + 1*d + 7add + 2*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      iX2 = i*X2
      C2 = Y2+iX2
      D2 = Y2-iX2
      iX1 = i*X1
      C1 = Y1+iX1
      D1 = Y1-iX1
      A = Z1*Z2
      B = 2*A^²
      C = C1*C2
      D = D1*D2
      L = D+C
      M = Y1*Y2
      N = 2*M-L
      E = d*M*N
      F = B-E
      G = B+E
      X3 = i*A*F*(D-C)
      Y3 = A*G*L
      Z3 = c*G*F

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

Assumptions: k*c=1.
Cost: 11M + 1*k + 8add.
Source: 2008.02.25 Hisil–Wong–Carter–Dawson, page 8.

Explicit formulas:

      A = X1*Z2
      B = Y1*Z2
      C = Z1*X2
      D = Z1*Y2
      E = A*B
      F = C*D
      G = E+F
      H = E-F
      J = (A-C)*(B+D)-H
      K = (A+D)*(B+C)-G
      X3 = G*J
      Y3 = H*K
      Z3 = k*J*K

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

Assumptions: c2=2*c.
Cost: 7M + 5S + 1*c2 + 1*d + 13add + 1*2.
Cost: 7M + 5S + 1*c2 + 1*d + 12add + 1*2 dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      A = Z1*Z2
      B = A^²
      C = X1*X2
      D = Y1*Y2
      E = d*C*D
      BB = B^²
      EE = E^²
      H = (A+B)^²-BB
      I = (A+E)^²-EE
      X3 = (H-I)*((X1+Y1)*(X2+Y2)-C-D)
      Y3 = (H+I-2*B)*(D-C)
      Z3 = c2*(BB-EE)

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

Assumptions: k*c=1.
Cost: 10M + 3S + 1*k + 13add + 2*2.
Cost: 9M + 2S + 1*k + 13add + 2*2 dependent upon the first point.
Source: 2009.03.11 Hisil–Wong–Carter–Dawson, after formula (17), plus denominator elimination.

Explicit formulas:

      R1 = X2*Y2
      R2 = Z2^²
      A = X1*Y1
      B = Z1^²
      C = R2*A
      D = R1*B
      E = (X1-X2)*(Y1+Y2)-A+R1
      F = (X1+Y2)*(Y1+X2)-A-R1
      G = (Z1+Z2)^²-B-R2
      X3 = 2*E*(C+D)
      Y3 = 2*F*(C-D)
      Z3 = k*E*F*G

Explicit formulas for doubling

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

Assumptions: cc2=2*c*c and Z1=1.
Cost: 3M + 3S + 2*c + 5add.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      B = (X1+Y1)^²
      C = X1^²
      D = Y1^²
      E = C+D
      J = E-cc2
      X3 = c*(B-E)*J
      Y3 = c*E*(C-D)
      Z3 = E*J

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

Cost: 3M + 4S + 3*c + 5add + 1*2.
Source: 2007 Bernstein–Lange; source comments that these formulas use two temporary registers.

Explicit formulas:

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

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

Cost: 3M + 4S + 3*c + 5add + 1*2.
Source: 2007 Bernstein–Lange.

Explicit formulas:

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

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

Cost: 3M + 4S + 3*c + 5add + 2*2.
Source: 2007 Bernstein–Lange; source comments that these formulas use one temporary register.

Explicit formulas:

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

Explicit formulas for tripling

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

Assumptions: c2=2*c.
Cost: 9M + 4S + 1*c2 + 6add + 1*2.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

      XX = X1^²
      YY = Y1^²
      ZZ = (c2*Z1)^²
      D = XX+YY
      DD = D^²
      H = 2*D*(XX-YY)
      P = DD-YY*ZZ
      Q = DD-XX*ZZ
      T = H+Q
      U = H-P
      X3 = P*U*X1
      Y3 = Q*T*Y1
      Z3 = T*U*Z1

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

Cost: 9M + 4S + 1*c + 13add + 2*2.
Source: 2007 Hisil–Carter–Dawson.

Explicit formulas:

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

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

Assumptions: c=1.
Cost: 7M + 7S + 12add + 2*2 + 1*4.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

      XX = X1^²
      YY = Y1^²
      ZZ = Z1^²
      ZZ4 = 4*ZZ
      D = XX+YY
      DD = D^²
      H = 2*D*(XX-YY)
      P = DD-YY*ZZ4
      Q = DD-XX*ZZ4
      T = H+Q
      TT = T^²
      U = H-P
      X3 = 2*P*U*X1
      Y3 = Q*((T+Y1)^²-TT-YY)
      Z3 = U*((T+Z1)^²-TT-ZZ)

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

Assumptions: cc4=4*c*c.
Cost: 7M + 7S + 1*cc4 + 12add + 2*2.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

      XX = X1^²
      YY = Y1^²
      ZZ = Z1^²
      ZZ4 = cc4*ZZ
      D = XX+YY
      DD = D^²
      H = 2*D*(XX-YY)
      P = DD-YY*ZZ4
      Q = DD-XX*ZZ4
      T = H+Q
      TT = T^²
      U = H-P
      X3 = 2*P*U*X1
      Y3 = Q*((T+Y1)^²-TT-YY)
      Z3 = U*((T+Z1)^²-TT-ZZ)

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 = X1*A
      Y3 = Y1*A
      Z3 = 1