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

Inverted 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^²)

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

  x=Z/X
  y=Z/Y

This representation was introduced in the Bernstein–Lange paper "Inverted Edwards coordinates" (AAECC 2007). This representation does not cover the points (0,+-c) and (+-c,0).

Best operation counts

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

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

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

9.8M for addition: 9M+1S.
8.8M for addition with Z2=1: 8M+1S.
8.8M for addition with X2=1: 8M+1S.
7M for addition with Z1=1 and Z2=1: 7M.
9.8M for readdition: 9M+1S after 9M+1S.
8.8M for readdition with Z2=1: 8M+1S after 8M+1S.
8.8M for readdition with X2=1: 8M+1S after 8M+1S.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
6.2M for doubling: 3M+4S.
5.4M for doubling with Z1=1: 3M+3S.
12.2M for tripling: 9M+4S.
102M for scaling: 1I+2M.

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

9.67M for addition: 9M+1S.
8.67M for addition with Z2=1: 8M+1S.
8.67M for addition with X2=1: 8M+1S.
7M for addition with Z1=1 and Z2=1: 7M.
9.67M for readdition: 9M+1S after 9M+1S.
8.67M for readdition with Z2=1: 8M+1S after 8M+1S.
8.67M for readdition with X2=1: 8M+1S after 8M+1S.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
5.68M for doubling: 3M+4S.
5.01M for doubling with Z1=1: 3M+3S.
11.68M for tripling: 9M+4S.
102M for scaling: 1I+2M.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	7M + 2*c	7M + 2*c
addition	X2=1	8M + 1S + 2c + 1d	8M + 1S + 2c + 1d
addition	Z2=1	8M + 1S + 2c + 1d	8M + 1S + 2c + 1d
addition	Z2=1	9M + 1*c	9M + 1*c
addition		9M + 1S + 2c + 1d	9M + 1S + 2c + 1d
addition		11M + 1*c	11M + 1*c
doubling	ccd2=2cc*d and Z1=1	3M + 3S + 1*c
doubling	ccd2=2cc*d	3M + 4S + 1ccd2 + 1c
tripling		9M + 4S + 1c + 1d
tripling	ccd=ccd	7M + 7S + 1*ccd
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: 7M + 2*c + 7add.
Cost: 7M + 2*c + 6add dependent upon the first point.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      C = X1*X2
      D = Y1*Y2
      E = C*D
      H = C-D
      I = (X1+Y1)*(X2+Y2)-C-D
      X3 = c*(E+d)*H
      Y3 = c*(E-d)*I
      Z3 = H*I

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

Assumptions: X2=1.
Cost: 8M + 1S + 2*c + 1*d + 4add.
Source: 2007 Bernstein–Lange.
Strongly unified.

Explicit formulas:

      A = Z1*Z2
      B = d*A^²
      D = Y1*Y2
      E = X1*D
      F = E-B
      G = E+B
      H = X1-D
      I = X1*Y2+Y1
      X3 = c*G*H
      Y3 = c*F*I
      Z3 = A*H*I

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

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

Explicit formulas:

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

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

Assumptions: Z2=1.
Cost: 9M + 1*c + 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
      X3 = ((A+D)*(B+C)-G)*H
      Y3 = ((A-C)*(B+D)-H)*G
      Z3 = c*G*H

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

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

Explicit formulas:

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

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

Cost: 11M + 1*c + 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
      X3 = ((A+D)*(B+C)-G)*H
      Y3 = ((A-C)*(B+D)-H)*G
      Z3 = c*G*H

Explicit formulas for doubling

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

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

Explicit formulas:

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

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

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

Explicit formulas:

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

Explicit formulas for tripling

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

Cost: 9M + 4S + 1*c + 1*d + 7add + 1*2 + 1*4.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      XX = X1^²
      YY = Y1^²
      ZZ = (c*Z1)^²
      D = XX+YY
      DD = D^²
      E = 4*(D-d*ZZ)
      H = 2*D*(YY-XX)
      P = DD-XX*E
      Q = DD-YY*E
      X3 = (H+Q)*Q*X1
      Y3 = (H-P)*P*Y1
      Z3 = P*Q*Z1

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

Assumptions: ccd=c*c*d.
Cost: 7M + 7S + 1*ccd + 13add + 2*2 + 1*4.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      XX = X1^²
      YY = Y1^²
      ZZ = Z1^²
      D = XX+YY
      DD = D^²
      E = 4*(D-ccd*ZZ)
      H = 2*D*(YY-XX)
      P = DD-XX*E
      Q = DD-YY*E
      QQ = Q^²
      X3 = (H+Q)*((Q+X1)^²-QQ-XX)
      Y3 = 2*(H-P)*P*Y1
      Z3 = P*((Q+Z1)^²-QQ-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