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

# Jacobian coordinates with a4=-3 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
```

Jacobian coordinates with a4=-3 [database entry] make the additional assumptions

```  a=-3
```
and represent x y as X Y Z satisfying the following equations:
```  x=X/Z^2
y=Y/Z^3
```

## 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 4M + 2S 4M + 2S
addition Z1=Z2 5M + 2S 5M + 2S
addition Z2=1 7M + 4S 7M + 4S
addition Z2=1 8M + 3S 8M + 3S
addition Z2=1 8M + 3S 8M + 3S
addition Z2=1 8M + 3S 8M + 3S
addition 11M + 5S 10M + 4S
addition 12M + 4S 11M + 3S
addition 12M + 4S 11M + 3S
addition half*2=1 12M + 4S + 1*half 11M + 3S + 1*half
addition 8M + 6S + 23 8M + 5S + 13
addition 10M + 5S + 33 10M + 4S + 23
addition 10M + 5S + 43 10M + 4S + 33
doubling Z1=1 1M + 5S
doubling 3M + 5S
doubling 2*half=1 4M + 4S + 1*half
doubling 2*half=1 4M + 4S + 1*half
doubling 1M + 8S + 1*a
doubling 3M + 6S + 1*a
doubling half*2=1 3M + 6S + 1*half + 1*a
doubling 4M + 4S + 14
doubling 3M + 3S + 24 + 1*a
doubling 3M + 3S + 24 + 1*a
tripling 7M + 7S
tripling 5M + 10S + 1*a
tripling 8M + 7S + 1*a
tripling 9M + 5S + 13 + 24 + 1*a
scaling 1I + 3M + 1S

## 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: 4M + 2S + 6add + 4*2 + 1*4.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      H = X2-X1
HH = H^2
I = 4*HH
J = H*I
r = 2*(Y2-Y1)
V = X1*I
X3 = r^2-J-2*V
Y3 = r*(V-X3)-2*Y1*J
Z3 = 2*H
```

The "zadd-2007-m" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z1=Z2.
• Cost: 5M + 2S + 9add.
• Source: 2007 Meloni "New point addition formulae for ECC applications", page 192.
• Explicit formulas:
```      A = (X2-X1)^2
B = X1*A
C = X2*A
D = (Y2-Y1)^2
X3 = D-B-C
Y3 = (Y2-Y1)*(B-X3)-Y1*(C-B)
Z3 = Z1*(X2-X1)
```

The "madd-2007-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z2=1.
• Cost: 7M + 4S + 9add + 3*2 + 1*4.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      Z1Z1 = Z1^2
U2 = X2*Z1Z1
S2 = Y2*Z1*Z1Z1
H = U2-X1
HH = H^2
I = 4*HH
J = H*I
r = 2*(S2-Y1)
V = X1*I
X3 = r^2-J-2*V
Y3 = r*(V-X3)-2*Y1*J
Z3 = (Z1+H)^2-Z1Z1-HH
```

The "madd-2004-hmv" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z2=1.
• Cost: 8M + 3S + 6add + 1*2.
• Source: 2004 Hankerson–Menezes–Vanstone, page 91.
• Explicit formulas:
```      T1 = Z1^2
T2 = T1*Z1
T1 = T1*X2
T2 = T2*Y2
T1 = T1-X1
T2 = T2-Y1
Z3 = Z1*T1
T3 = T1^2
T4 = T3*T1
T3 = T3*X1
T1 = 2*T3
X3 = T2^2
X3 = X3-T1
X3 = X3-T4
T3 = T3-X3
T3 = T3*T2
T4 = T4*Y1
Y3 = T3-T4
```

The "madd-2008-g" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z2=1.
• Cost: 8M + 3S + 6add + 1*2.
• Source: 2008 Giessmann.
• Explicit formulas:
```      T1 = Z1^2
T2 = T1*Z1
T1 = T1*X2
T2 = T2*Y2
T1 = X1-T1
T2 = T2-Y1
Z3 = Z1*T1
T4 = T1^2
T1 = T1*T4
T4 = T4*X1
X3 = T2^2
X3 = X3+T1
Y3 = T1*Y1
T1 = 2*T4
X3 = X3-T1
T4 = X3-T4
T4 = T4*T2
Y3 = T4-Y3
```

The "madd" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: Z2=1.
• Cost: 8M + 3S + 6add + 5*2.
• Explicit formulas:
```      Z1Z1 = Z1^2
U2 = X2*Z1Z1
S2 = Y2*Z1*Z1Z1
H = U2-X1
I = (2*H)^2
J = H*I
r = 2*(S2-Y1)
V = X1*I
X3 = r^2-J-2*V
Y3 = r*(V-X3)-2*Y1*J
Z3 = 2*Z1*H
```

The "add-2007-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 11M + 5S + 9add + 4*2.
• Cost: 10M + 4S + 9add + 4*2 dependent upon the first point.
• Source: 2007 Bernstein–Lange; note that the improvement from 12M+4S to 11M+5S was already mentioned in 2001 Bernstein http://cr.yp.to/talks.html#2001.10.29.
• Explicit formulas:
```      Z1Z1 = Z1^2
Z2Z2 = Z2^2
U1 = X1*Z2Z2
U2 = X2*Z1Z1
S1 = Y1*Z2*Z2Z2
S2 = Y2*Z1*Z1Z1
H = U2-U1
I = (2*H)^2
J = H*I
r = 2*(S2-S1)
V = U1*I
X3 = r^2-J-2*V
Y3 = r*(V-X3)-2*S1*J
Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2)*H
```

The "add-1998-cmo-2" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 12M + 4S + 6add + 1*2.
• Cost: 11M + 3S + 6add + 1*2 dependent upon the first point.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (5), plus common-subexpression elimination.
• Explicit formulas:
```      Z1Z1 = Z1^2
Z2Z2 = Z2^2
U1 = X1*Z2Z2
U2 = X2*Z1Z1
S1 = Y1*Z2*Z2Z2
S2 = Y2*Z1*Z1Z1
H = U2-U1
HH = H^2
HHH = H*HH
r = S2-S1
V = U1*HH
X3 = r^2-HHH-2*V
Y3 = r*(V-X3)-S1*HHH
Z3 = Z1*Z2*H
```

The "add-2001-b" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 12M + 4S + 6add + 1*2.
• Cost: 11M + 3S + 6add + 1*2 dependent upon the first point.
• Source: 2001 Bernstein http://cr.yp.to/nistp224.html opt-idea53.c ecadd.
• Explicit formulas:
```      ZZ1 = Z1^2
ZZZ1 = Z1*ZZ1
ZZ2 = Z2^2
ZZZ2 = Z2*ZZ2
A = X1*ZZ2
B = X2*ZZ1-A
c = Y1*ZZZ2
d = Y2*ZZZ1-c
e = B^2
f = B*e
g = A*e
h = Z1*Z2
f2g = 2*g+f
X3 = d^2-f2g
Z3 = B*h
gx = g-X3
Y3 = d*gx-c*f
```

The "add-1998-hnm" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: half*2=1.
• Cost: 12M + 4S + 1*half + 8add + 2*2.
• Cost: 11M + 3S + 1*half + 8add + 2*2 dependent upon the first point.
• Source: 1998 Hasegawa–Nakajima–Matsui, page 188.
• Explicit formulas:
```      R1 = X1
R2 = Y1
R3 = Z1
R4 = X2
R5 = Y2
R6 = Z2
R7 = R6^2
R1 = R1*R7
R7 = R6*R7
R2 = R2*R7
R7 = R3^2
R8 = R4*R7
R7 = R3*R7
R7 = R5*R7
R2 = R2-R7
R7 = 2*R7
R7 = R2+R7
R1 = R1-R8
R8 = 2*R8
R8 = R1+R8
R3 = R3*R6
R3 = R3*R1
R7 = R7*R1
R1 = R1^2
R8 = R8*R1
R7 = R7*R1
R1 = R2^2
R1 = R1-R8
R8 = R8-R1
R8 = R8-R1
R8 = R8*R2
R2 = R8-R7
R2 = half*R2
X3 = R1
Y3 = R2
Z3 = R3
```

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

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

The "add-1998-cmo" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 10M + 5S + 43 + 6add + 1*2.
• Cost: 10M + 4S + 33 + 6add + 1*2 dependent upon the first point.
• Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (5).
• Explicit formulas:
```      U1 = X1*Z2^2
U2 = X2*Z1^2
S1 = Y1*Z2^3
S2 = Y2*Z1^3
H = U2-U1
r = S2-S1
X3 = r^2-H^3-2*U1*H^2
Y3 = r*(U1*H^2-X3)-S1*H^3
Z3 = Z1*Z2*H
```

## Explicit formulas for doubling

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

The "dbl-2001-b" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 3M + 5S + 8add + 1*3 + 1*4 + 2*8.
• Source: 2001 Bernstein "A software implementation of NIST P-224".
• Explicit formulas:
```      delta = Z1^2
gamma = Y1^2
beta = X1*gamma
alpha = 3*(X1-delta)*(X1+delta)
X3 = alpha^2-8*beta
Z3 = (Y1+Z1)^2-gamma-delta
Y3 = alpha*(4*beta-X3)-8*gamma^2
```

The "dbl-2004-hmv" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: 2*half=1.
• Cost: 4M + 4S + 1*half + 5add + 2*2 + 1*3.
• Source: 2004 Hankerson–Menezes–Vanstone, page 91.
• Explicit formulas:
```      T1 = Z1^2
T2 = X1-T1
T1 = X1+T1
T2 = T2*T1
T2 = 3*T2
Y3 = 2*Y1
Z3 = Y3*Z1
Y3 = Y3^2
T3 = Y3*X1
Y3 = Y3^2
Y3 = half*Y3
X3 = T2^2
T1 = 2*T3
X3 = X3-T1
T1 = T3-X3
T1 = T1*T2
Y3 = T1-Y3
```

The "dbl-1998-hnm-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: 2*half=1.
• Cost: 4M + 4S + 1*half + 7add + 3*2.
• Source: 1998 Hasegawa–Nakajima–Matsui, page 188.
• Explicit formulas:
```      R1 = X1
R2 = Y1
R3 = Z1
R4 = R3^2
R3 = R2*R3
R3 = 2*R3
R5 = R1-R4
R4 = R1+R4
R5 = R4*R5
R4 = 2*R5
R4 = R4+R5
R2 = 2*R2
R2 = R2^2
R5 = R2^2
R5 = half*R5
R2 = R2*R1
R1 = R4^2
R1 = R1-R2
R1 = R1-R2
R2 = R2-R1
R2 = R2*R4
R2 = R2-R5
X3 = R1
Y3 = R2
Z3 = R3
```

The "dbl-2007-bl" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 1M + 8S + 1*a + 10add + 2*2 + 1*3 + 1*8.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      XX = X1^2
YY = Y1^2
YYYY = YY^2
ZZ = Z1^2
S = 2*((X1+YY)^2-XX-YYYY)
M = 3*XX+a*ZZ^2
T = M^2-2*S
X3 = T
Y3 = M*(S-T)-8*YYYY
Z3 = (Y1+Z1)^2-YY-ZZ
```

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

The "dbl-1998-hnm" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: half*2=1.
• Cost: 3M + 6S + 1*half + 1*a + 6add + 3*2.
• Source: 1998 Hasegawa–Nakajima–Matsui, page 188.
• Explicit formulas:
```      R1 = X1
R2 = Y1
R3 = Z1
R4 = R3^2
R3 = R2*R3
R3 = 2*R3
R4 = R4^2
R4 = a*R4
R5 = R1^2
R4 = R4+R5
R5 = 2*R5
R4 = R4+R5
R2 = 2*R2
R2 = R2^2
R5 = R2^2
R5 = half*R5
R2 = R2*R1
R1 = R4^2
R1 = R1-R2
R1 = R1-R2
R2 = R2-R1
R2 = R2*R4
R2 = R2-R5
X3 = R1
Y3 = R2
Z3 = R3
```

The "dbl-1986-cc-2" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 4M + 4S + 14 + 5add + 2*2 + 1*3 + 1*4 + 1*8.
• Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", page 414, formula (4.2ii) modified as indicated after "It is even smarter ...".
• Explicit formulas:
```      S = 4*X1*Y1^2
M = 3*(X1-Z1^2)*(X1+Z1^2)
T = M^2-2*S
X3 = T
Y3 = M*(S-T)-8*Y1^4
Z3 = 2*Y1*Z1
```

The "dbl-1986-cc" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 3M + 3S + 24 + 1*a + 4add + 2*2 + 1*3 + 1*4 + 1*8.
• Source: 1986 Chudnovsky–Chudnovsky "Sequences of numbers generated by addition in formal groups and new primality and factorization tests", page 414, formula (4.2ii).
• Explicit formulas:
```      S = 4*X1*Y1^2
M = 3*X1^2+a*Z1^4
T = M^2-2*S
X3 = T
Y3 = M*(S-T)-8*Y1^4
Z3 = 2*Y1*Z1
```

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

## Explicit formulas for tripling

The "tpl-2007-bl-2" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 7M + 7S + 13add + 1*3 + 2*4 + 1*8 + 1*12 + 1*16.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      YY = Y1^2
ZZ = Z1^2
YYYY = YY^2
M = 3*(X1-ZZ)*(X1+ZZ)
MM = M^2
E = 12*X1*YY-MM
EE = E^2
T = 16*YYYY
U = (M+E)^2-MM-EE-T
X3 = 4*(X1*EE-4*YY*U)
Y3 = 8*Y1*(U*(T-U)-E*EE)
Z3 = (Z1+E)^2-ZZ-EE
```

The "tpl-2007-bl" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 5M + 10S + 1*a + 15add + 1*3 + 2*4 + 1*6 + 1*8 + 1*16.
• Source: 2007 Bernstein–Lange.
• Explicit formulas:
```      XX = X1^2
YY = Y1^2
ZZ = Z1^2
YYYY = YY^2
M = 3*XX+a*ZZ^2
MM = M^2
E = 6*((X1+YY)^2-XX-YYYY)-MM
EE = E^2
T = 16*YYYY
U = (M+E)^2-MM-EE-T
X3 = 4*(X1*EE-4*YY*U)
Y3 = 8*Y1*(U*(T-U)-E*EE)
Z3 = (Z1+E)^2-ZZ-EE
```

The "tpl-2005-dim-2" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 8M + 7S + 1*a + 6add + 2*2 + 1*3 + 1*4 + 1*6.
• Source: 2005 Dimitrov–Imbert–Mishra, plus common-subexpression elimination.
• Explicit formulas:
```      ZZ = Z1^2
YY = Y1^2
C = 2*YY
M = 3*X1^2+a*ZZ^2
E = 6*X1*C-M^2
EE = E^2
T = 2*C^2
U = M*E-T
U4 = 4*U
X3 = X1*EE-C*U4
Y3 = Y1*(U4*(T-U)-E*EE)
Z3 = Z1*E
```

The "tpl-2005-dim" tripling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 9M + 5S + 13 + 24 + 1*a + 7add + 1*2 + 1*3 + 1*4 + 2*8 + 1*12.
• Source: 2005 Dimitrov–Imbert–Mishra.
• Explicit formulas:
```      M = 3*X1^2+a*Z1^4
E = 12*X1*Y1^2-M^2
T = 8*Y1^4
X3 = 8*Y1^2*(T-M*E)+X1*E^2
Y3 = Y1*(4*(M*E-T)*(2*T-M*E)-E^3)
Z3 = Z1*E
```

## Explicit formulas for scaling

The "z" scaling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 1I + 3M + 1S + 0add.
• Explicit formulas:
```      A = 1/Z1
AA = A^2
X3 = X1*AA
Y3 = Y1*AA*A
Z3 = 1
```