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

Extended coordinates for twisted Edwards curves

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

  a*x^²+y^²=1+d*x^²*y^²

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

  x=X/Z
  y=Y/Z
  x*y=T/Z

This representation was introduced in the Hisil–Wong–Carter–Dawson paper "Twisted Edwards curves revisited" (Asiacrypt 2008).

Best operation counts

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

9M for addition: 9M. 9M.
8M for addition with Z2=1: 8M. 8M.
7M for addition with Z1=1 and Z2=1: 7M.
9M for readdition: 9M after 9M. 9M after 9M.
8M for readdition with Z2=1: 8M after 8M. 8M after 8M.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
8M for doubling: 4M+4S.
7M for doubling with Z1=1: 3M+4S.
14M for tripling: 11M+3S.

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

9M for addition: 9M. 9M.
8M for addition with Z2=1: 8M. 8M.
7M for addition with Z1=1 and Z2=1: 7M.
9M for readdition: 9M after 9M. 9M after 9M.
8M for readdition with Z2=1: 8M after 8M. 8M after 8M.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
7.2M for doubling: 4M+4S.
6.2M for doubling with Z1=1: 3M+4S.
13.4M for tripling: 11M+3S.

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

9M for addition: 9M. 9M.
8M for addition with Z2=1: 8M. 8M.
7M for addition with Z1=1 and Z2=1: 7M.
9M for readdition: 9M after 9M. 9M after 9M.
8M for readdition with Z2=1: 8M after 8M. 8M after 8M.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
6.68M for doubling: 4M+4S.
5.68M for doubling with Z1=1: 3M+4S.
13.01M for tripling: 11M+3S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	7M + 1*a	7M + 1*a
addition	Z1=1 and Z2=1	7M + 1S + 1a + 1d	7M + 1S + 1*a
addition	Z2=1	8M + 1*a	8M + 1*a
addition	Z2=1	8M + 1a + 1d	8M + 1*a
addition		9M + 1*a	9M + 1*a
addition		9M + 1a + 1d	9M + 1*a
doubling	Z1=1	3M + 4S + 1*a
doubling		4M + 4S + 1*a
tripling		11M + 3S + 1*a

Explicit formulas for addition

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

Assumptions: Z1=1 and Z2=1.
Cost: 7M + 1*a + 7add.
Cost: 7M + 1*a + 6add dependent upon the first point.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2, plus assumption Z1=1.

Explicit formulas:

      A = X1*X2
      B = Y1*Y2
      C = T2
      D = T1
      E = D+C
      F = (X1-Y1)*(X2+Y2)+B-A
      G = B+a*A
      H = D-C
      X3 = E*F
      Y3 = G*H
      T3 = E*H
      Z3 = F*G

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

Assumptions: Z1=1 and Z2=1.
Cost: 7M + 1S + 1*a + 1*d + 8add.
Cost: 7M + 1S + 1*a + 7add dependent upon the first point.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1, plus assumption Z1=1, plus standard simplification.
Strongly unified.

Explicit formulas:

      A = X1*X2
      B = Y1*Y2
      C = T1*d*T2
      E = (X1+Y1)*(X2+Y2)-A-B
      F = 1-C
      G = 1+C
      H = B-a*A
      X3 = E*F
      Y3 = G*H
      T3 = E*H
      Z3 = 1-C^²

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

Assumptions: Z2=1.
Cost: 8M + 1*a + 7add.
Cost: 8M + 1*a + 6add dependent upon the first point.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2.

Explicit formulas:

      A = X1*X2
      B = Y1*Y2
      C = Z1*T2
      D = T1
      E = D+C
      F = (X1-Y1)*(X2+Y2)+B-A
      G = B+a*A
      H = D-C
      X3 = E*F
      Y3 = G*H
      T3 = E*H
      Z3 = F*G

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

Assumptions: Z2=1.
Cost: 8M + 1*a + 1*d + 7add.
Cost: 8M + 1*a + 6add dependent upon the first point.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1.
Strongly unified.

Explicit formulas:

      A = X1*X2
      B = Y1*Y2
      C = T1*d*T2
      D = Z1
      E = (X1+Y1)*(X2+Y2)-A-B
      F = D-C
      G = D+C
      H = B-a*A
      X3 = E*F
      Y3 = G*H
      T3 = E*H
      Z3 = F*G

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

Cost: 9M + 1*a + 7add.
Cost: 9M + 1*a + 6add dependent upon the first point.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.2.

Explicit formulas:

      A = X1*X2
      B = Y1*Y2
      C = Z1*T2
      D = T1*Z2
      E = D+C
      F = (X1-Y1)*(X2+Y2)+B-A
      G = B+a*A
      H = D-C
      X3 = E*F
      Y3 = G*H
      T3 = E*H
      Z3 = F*G

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

Cost: 9M + 1*a + 1*d + 7add.
Cost: 9M + 1*a + 6add dependent upon the first point.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.1.
Strongly unified.

Explicit formulas:

      A = X1*X2
      B = Y1*Y2
      C = T1*d*T2
      D = Z1*Z2
      E = (X1+Y1)*(X2+Y2)-A-B
      F = D-C
      G = D+C
      H = B-a*A
      X3 = E*F
      Y3 = G*H
      T3 = E*H
      Z3 = F*G

Explicit formulas for doubling

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

Assumptions: Z1=1.
Cost: 3M + 4S + 1*a + 7add + 1*2.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.3, plus assumption Z1=1, plus standard simplification.

Explicit formulas:

      A = X1^²
      B = Y1^²
      D = a*A
      E = (X1+Y1)^²-A-B
      G = D+B
      H = D-B
      X3 = E*(G-2)
      Y3 = G*H
      T3 = E*H
      Z3 = G^²-2*G

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

Cost: 4M + 4S + 1*a + 6add + 1*2.
Source: 2008 Hisil–Wong–Carter–Dawson, http://eprint.iacr.org/2008/522, Section 3.3.

Explicit formulas:

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

Explicit formulas for tripling

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

Cost: 11M + 3S + 1*a + 7add + 2*2.
Source: 2015 Chuengsatiansup.

Explicit formulas:

      YY = Y1^²
      aXX = a*X1^²
      Ap = YY+aXX
      B = 2*(2*Z1^²-Ap)
      xB = aXX*B
      yB = YY*B
      AA = Ap*(YY-aXX)
      F = AA-yB
      G = AA+xB
      xE = X1*(yB+AA)
      yH = Y1*(xB-AA)
      zF = Z1*F
      zG = Z1*G
      X3 = xE*zF
      Y3 = yH*zG
      Z3 = zF*zG
      T3 = xE*yH

Extended coordinates for twisted Edwards curves

Best operation counts

Summary of all explicit formulas

Explicit formulas for addition

Explicit formulas for doubling

Explicit formulas for tripling

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

Explicit formulas for scaling