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^2+y^2=1+d*x^2*y^2
```

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:
Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:
Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:

## Summary of all explicit formulas

OperationAssumptionsCostReaddition cost
addition Z1=1 and Z2=1 7M + 1*a 7M + 1*a
addition Z1=1 and Z2=1 7M + 1S + 1*a + 1*d 7M + 1S + 1*a
addition Z2=1 8M + 1*a 8M + 1*a
addition Z2=1 8M + 1*a + 1*d 8M + 1*a
addition 9M + 1*a 9M + 1*a
addition 9M + 1*a + 1*d 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^2
```

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^2
B = Y1^2
D = a*A
E = (X1+Y1)^2-A-B
G = D+B
H = D-B
X3 = E*(G-2)
Y3 = G*H
T3 = E*H
Z3 = G^2-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^2
B = Y1^2
C = 2*Z1^2
D = a*A
E = (X1+Y1)^2-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^2
aXX = a*X1^2
Ap = YY+aXX
B = 2*(2*Z1^2-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
```