Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Short Weierstrass curves EFD / Genus-1 large-characteristic / Projective coordinates with a4=-1 for short Weierstrass curves

# Projective coordinates with a4=-1 for short Weierstrass curves

An elliptic curve in short Weierstrass form [more information] has parameters a b and coordinates x y satisfying the following equations:
```  y^2=x^3+a*x+b
```

Projective coordinates with a4=-1 [database entry] make the additional assumptions

```  a=-1
```
and 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 5M + 2S 5M + 2S
addition Z2=1 9M + 2S 9M + 2S
addition Z2=1 and b3=3*b 11M + 2*b3 + 3*a 11M + 2*b3 + 3*a
addition b3=3*b 12M + 2*b3 + 3*a 12M + 2*b3 + 3*a
addition 12M + 2S 12M + 2S
addition 13M + 3S 13M + 3S
addition 11M + 6S + 1*a 11M + 6S + 1*a
addition 12M + 5S + 1*a 12M + 5S + 1*a
addition 10M + 4S + 13 10M + 4S + 13
addition 16M + 3S + 33 16M + 3S + 33
doubling Z1=1 3M + 5S
doubling 5M + 6S + 1*a
doubling 6M + 5S + 1*a
doubling b3=3*b 8M + 3S + 2*b3 + 3*a
doubling 6M + 5S + 13 + 1*a
scaling 1I + 2M

The "mmadd-1998-cmo" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z1=1 and Z2=1.
• Cost: 5M + 2S + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", plus Z1=1, plus Z2=1, plus common-subexpression elimination.
• Explicit formulas:
```      u = Y2-Y1
uu = u^2
v = X2-X1
vv = v^2
vvv = v*vv
R = vv*X1
A = uu-vvv-2*R
X3 = v*A
Y3 = u*(R-A)-vvv*Y1
Z3 = vvv
```

The "madd-1998-cmo" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z2=1.
• Cost: 9M + 2S + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (3), plus common-subexpression elimination, plus Z2=1.
• Explicit formulas:
```      u = Y2*Z1-Y1
uu = u^2
v = X2*Z1-X1
vv = v^2
vvv = v*vv
R = vv*X1
A = uu*Z1-vvv-2*R
X3 = v*A
Y3 = u*(R-A)-vvv*Y1
Z3 = vvv*Z1
```

The "madd-2015-rcb" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z2=1 and b3=3*b.
• Cost: 11M + 2*b3 + 3*a + 17add.
• Cost: 11M + 2*b3 + 3*a + 16add dependent upon the first point.
• Source: 2015 Renes–Costello–Batina "Complete addition formulas for prime order elliptic curves", Algorithm 2.
• Strongly unified.
• Explicit formulas:
```      t0 = X1*X2
t1 = Y1*Y2
t3 = X2+Y2
t4 = X1+Y1
t3 = t3*t4
t4 = t0+t1
t3 = t3-t4
t4 = X2*Z1
t4 = t4+X1
t5 = Y2*Z1
t5 = t5+Y1
Z3 = a*t4
X3 = b3*Z1
Z3 = X3+Z3
X3 = t1-Z3
Z3 = t1+Z3
Y3 = X3*Z3
t1 = t0+t0
t1 = t1+t0
t2 = a*Z1
t4 = b3*t4
t1 = t1+t2
t2 = t0-t2
t2 = a*t2
t4 = t4+t2
t0 = t1*t4
Y3 = Y3+t0
t0 = t5*t4
X3 = t3*X3
X3 = X3-t0
t0 = t3*t1
Z3 = t5*Z3
Z3 = Z3+t0
```

The "add-2015-rcb" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: b3=3*b.
• Cost: 12M + 2*b3 + 3*a + 23add.
• Cost: 12M + 2*b3 + 3*a + 20add dependent upon the first point.
• Source: 2015 Renes–Costello–Batina "Complete addition formulas for prime order elliptic curves", Appendix A.1.
• Strongly unified.
• Explicit formulas:
```      t0 = X1*X2
t1 = Y1*Y2
t2 = Z1*Z2
t3 = X1+Y1
t4 = X2+Y2
t3 = t3*t4
t4 = t0+t1
t3 = t3-t4
t4 = X1+Z1
t5 = X2+Z2
t4 = t4*t5
t5 = t0+t2
t4 = t4-t5
t5 = Y1+Z1
X3 = Y2+Z2
t5 = t5*X3
X3 = t1+t2
t5 = t5-X3
Z3 = a*t4
X3 = b3*t2
Z3 = X3+Z3
X3 = t1-Z3
Z3 = t1+Z3
Y3 = X3*Z3
t1 = t0+t0
t1 = t1+t0
t2 = a*t2
t4 = b3*t4
t1 = t1+t2
t2 = t0-t2
t2 = a*t2
t4 = t4+t2
t0 = t1*t4
Y3 = Y3+t0
t0 = t5*t4
X3 = t3*X3
X3 = X3-t0
t0 = t3*t1
Z3 = t5*Z3
Z3 = Z3+t0
```

The "add-1998-cmo-2" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 12M + 2S + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (3), plus common-subexpression elimination.
• Explicit formulas:
```      Y1Z2 = Y1*Z2
X1Z2 = X1*Z2
Z1Z2 = Z1*Z2
u = Y2*Z1-Y1Z2
uu = u^2
v = X2*Z1-X1Z2
vv = v^2
vvv = v*vv
R = vv*X1Z2
A = uu*Z1Z2-vvv-2*R
X3 = v*A
Y3 = u*(R-A)-vvv*Y1Z2
Z3 = vvv*Z1Z2
```

The "add-2002-bj-2" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 13M + 3S + 8add + 3*2.
• Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", page 340.
• Strongly unified.
• Explicit formulas:
```      U1 = X1*Z2
U2 = X2*Z1
S1 = Y1*Z2
S2 = Y2*Z1
ZZ = Z1*Z2
T = U1+U2
M = S1+S2
R = (T-ZZ)*(T+ZZ)-U1*U2
F = ZZ*M
L = M*F
G = T*L
W = R^2-G
X3 = 2*F*W
Y3 = R*(G-2*W)-L^2
Z3 = 2*F*F^2
```

The "add-2007-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 11M + 6S + 1*a + 10add + 4*2 + 1*4.
• Source: 2007 Bernstein–Lange.
• Strongly unified.
• Explicit formulas:
```      U1 = X1*Z2
U2 = X2*Z1
S1 = Y1*Z2
S2 = Y2*Z1
ZZ = Z1*Z2
T = U1+U2
TT = T^2
M = S1+S2
R = TT-U1*U2+a*ZZ^2
F = ZZ*M
L = M*F
LL = L^2
G = (T+L)^2-TT-LL
W = 2*R^2-G
X3 = 2*F*W
Y3 = R*(G-2*W)-2*LL
Z3 = 4*F*F^2
```

The "add-2002-bj" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 12M + 5S + 1*a + 7add + 3*2.
• Source: 2002 Brier–Joye "Weierstrass elliptic curves and side-channel attacks", page 339.
• Strongly unified.
• Explicit formulas:
```      U1 = X1*Z2
U2 = X2*Z1
S1 = Y1*Z2
S2 = Y2*Z1
ZZ = Z1*Z2
T = U1+U2
M = S1+S2
R = T^2-U1*U2+a*ZZ^2
F = ZZ*M
L = M*F
G = T*L
W = R^2-G
X3 = 2*F*W
Y3 = R*(G-2*W)-L^2
Z3 = 2*F*F^2
```

The "add-1986-cc" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 10M + 4S + 13 + 7add + 1*2 + 1*3.
• Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", page 415, formula (4.4i).
• Explicit formulas:
```      U1 = X1*Z2
U2 = X2*Z1
S1 = Y1*Z2
S2 = Y2*Z1
W = Z1*Z2
P = U2-U1
R = S2-S1
X3 = P*(-(U1+U2)*P^2+W*R^2)
Y3 = (R*(-2*W*R^2+3*(U1+U2)*P^2)-P^3*(S1+S2))/2
Z3 = W*P^3
```

The "add-1998-cmo" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 16M + 3S + 33 + 6add + 1*2.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (3).
• Explicit formulas:
```      u = Y2*Z1-Y1*Z2
v = X2*Z1-X1*Z2
A = u^2*Z1*Z2-v^3-2*v^2*X1*Z2
X3 = v*A
Y3 = u*(v^2*X1*Z2-A)-v^3*Y1*Z2
Z3 = v^3*Z1*Z2
```

## Explicit formulas for doubling

The "mdbl-2007-bl" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z1=1.
• Cost: 3M + 5S + 7add + 4*2 + 1*3 + 1*4.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      XX = X1^2
w = a+3*XX
Y1Y1 = Y1^2
R = 2*Y1Y1
sss = 4*Y1*R
RR = R^2
B = (X1+R)^2-XX-RR
h = w^2-2*B
X3 = 2*h*Y1
Y3 = w*(B-h)-2*RR
Z3 = sss
```

The "dbl-2007-bl" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 5M + 6S + 1*a + 7add + 3*2 + 1*3.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      XX = X1^2
ZZ = Z1^2
w = a*ZZ+3*XX
s = 2*Y1*Z1
ss = s^2
sss = s*ss
R = Y1*s
RR = R^2
B = (X1+R)^2-XX-RR
h = w^2-2*B
X3 = h*s
Y3 = w*(B-h)-2*RR
Z3 = sss
```

The "dbl-1998-cmo-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 6M + 5S + 1*a + 4add + 1*2 + 1*3 + 1*4 + 3*8.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (4), plus common-subexpression elimination.
• Explicit formulas:
```      w = a*Z1^2+3*X1^2
s = Y1*Z1
ss = s^2
sss = s*ss
R = Y1*s
B = X1*R
h = w^2-8*B
X3 = 2*h*s
Y3 = w*(4*B-h)-8*R^2
Z3 = 8*sss
```

The "dbl-2015-rcb" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: b3=3*b.
• Cost: 8M + 3S + 2*b3 + 3*a + 15add.
• Source: 2015 Renes–Costello–Batina "Complete addition formulas for prime order elliptic curves", Appendix A.1.
• Explicit formulas:
```      t0 = X1^2
t1 = Y1^2
t2 = Z1^2
t3 = X1*Y1
t3 = t3+t3
Z3 = X1*Z1
Z3 = Z3+Z3
X3 = a*Z3
Y3 = b3*t2
Y3 = X3+Y3
X3 = t1-Y3
Y3 = t1+Y3
Y3 = X3*Y3
X3 = t3*X3
Z3 = b3*Z3
t2 = a*t2
t3 = t0-t2
t3 = a*t3
t3 = t3+Z3
Z3 = t0+t0
t0 = Z3+t0
t0 = t0+t2
t0 = t0*t3
Y3 = Y3+t0
t2 = Y1*Z1
t2 = t2+t2
t0 = t2*t3
X3 = X3-t0
Z3 = t2*t1
Z3 = Z3+Z3
Z3 = Z3+Z3
```

The "dbl-1998-cmo" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 6M + 5S + 13 + 1*a + 4add + 1*2 + 1*3 + 1*4 + 3*8.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (4).
• Explicit formulas:
```      w = a*Z1^2+3*X1^2
s = Y1*Z1
B = X1*Y1*s
h = w^2-8*B
X3 = 2*h*s
Y3 = w*(4*B-h)-8*Y1^2*s^2
Z3 = 8*s^3
```

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