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

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:
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

addition Z1=1 and Z2=1 6M + 1S + 1*c + 1*d 6M + 1S + 1*c + 1*d
addition k*c=1 and Z2=1 9M + 1*k 9M + 1*k
addition X2=1 9M + 1S + 1*c + 1*d 9M + 1S + 1*c + 1*d
addition Z2=1 9M + 1S + 1*c + 1*d 9M + 1S + 1*c + 1*d
addition Z2=1 9M + 1S + 1*c + 1*d 9M + 1S + 1*c + 1*d
addition c2=2*c and Z2=1 6M + 5S + 1*c2 + 1*d 6M + 5S + 1*c2 + 1*d
addition 10M + 1S + 1*c + 1*d 10M + 1S + 1*c + 1*d
addition 10M + 1S + 1*c + 1*d 10M + 1S + 1*c + 1*d
addition i2=-1 10M + 1S + 3*i + 1*c + 1*d 10M + 1S + 2*i + 1*c + 1*d
addition k*c=1 11M + 1*k 11M + 1*k
addition c2=2*c 7M + 5S + 1*c2 + 1*d 7M + 5S + 1*c2 + 1*d
addition k*c=1 10M + 3S + 1*k 9M + 2S + 1*k
doubling cc2=2*c*c 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=4*c*c 7M + 7S + 1*cc4
scaling 1I + 2M

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^2)
```

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^2
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^2
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^2
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^2
C = X1*X2
D = Y1*Y2
E = d*C*D
BB = B^2
EE = E^2
H = (Z1+B)^2-BB
I = (Z1+E)^2-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^2
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^2
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: i2=-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^2
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^2
C = X1*X2
D = Y1*Y2
E = d*C*D
BB = B^2
EE = E^2
H = (A+B)^2-BB
I = (A+E)^2-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^2
A = X1*Y1
B = Z1^2
C = R2*A
D = R1*B
E = (X1-X2)*(Y1+Y2)-A+R1
F = (X1+Y2)*(Y1+X2)-A-R1
G = (Z1+Z2)^2-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)^2
C = X1^2
D = Y1^2
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^2
R2 = R2^2
R3 = R3^2
R4 = R4^2
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)^2
C = X1^2
D = Y1^2
E = C+D
H = (c*Z1)^2
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^2
R1 = R1+R2
R1 = R1^2
R2 = R2^2
R3 = R3^2
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^2
YY = Y1^2
ZZ = (c2*Z1)^2
D = XX+YY
DD = D^2
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^2
B = Y1^2
C = (2*c*Z1)^2
D = (A+B)^2
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^2
YY = Y1^2
ZZ = Z1^2
ZZ4 = 4*ZZ
D = XX+YY
DD = D^2
H = 2*D*(XX-YY)
P = DD-YY*ZZ4
Q = DD-XX*ZZ4
T = H+Q
TT = T^2
U = H-P
X3 = 2*P*U*X1
Y3 = Q*((T+Y1)^2-TT-YY)
Z3 = U*((T+Z1)^2-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^2
YY = Y1^2
ZZ = Z1^2
ZZ4 = cc4*ZZ
D = XX+YY
DD = D^2
H = 2*D*(XX-YY)
P = DD-YY*ZZ4
Q = DD-XX*ZZ4
T = H+Q
TT = T^2
U = H-P
X3 = 2*P*U*X1
Y3 = Q*((T+Y1)^2-TT-YY)
Z3 = U*((T+Z1)^2-TT-ZZ)
```

## 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
```