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

Jacobian coordinates with a4=0 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^²=x^³+a*x+b

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

a=0

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:

16M for addition: 11M+5S. 12M+4S. 12M+4S. 12M+4S.
11M for addition with Z2=1: 7M+4S. 8M+3S. 8M+3S. 8M+3S.
7M for addition with Z1=Z2: 5M+2S.
6M for addition with Z1=1 and Z2=1: 4M+2S.
14M for readdition: 10M+4S after 11M+5S. 11M+3S after 12M+4S. 11M+3S after 12M+4S. 11M+3S after 12M+4S.
11M for readdition with Z2=1: 7M+4S after 7M+4S. 8M+3S after 8M+3S. 8M+3S after 8M+3S. 8M+3S after 8M+3S.
7M for readdition with Z1=Z2: 5M+2S after 5M+2S.
6M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
7M for doubling: 2M+5S.
6M for doubling with Z1=1: 1M+5S.
15M for tripling: 5M+10S. 8M+7S.
104M for scaling: 1I+3M+1S.

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

15M for addition: 11M+5S.
10.2M for addition with Z2=1: 7M+4S.
6.6M for addition with Z1=Z2: 5M+2S.
5.6M for addition with Z1=1 and Z2=1: 4M+2S.
13.2M for readdition: 10M+4S after 11M+5S.
10.2M for readdition with Z2=1: 7M+4S after 7M+4S.
6.6M for readdition with Z1=Z2: 5M+2S after 5M+2S.
5.6M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
6M for doubling: 2M+5S.
5M for doubling with Z1=1: 1M+5S.
13M for tripling: 5M+10S.
103.8M for scaling: 1I+3M+1S.

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

14.35M for addition: 11M+5S.
9.68M for addition with Z2=1: 7M+4S.
6.34M for addition with Z1=Z2: 5M+2S.
5.34M for addition with Z1=1 and Z2=1: 4M+2S.
12.68M for readdition: 10M+4S after 11M+5S.
9.68M for readdition with Z2=1: 7M+4S after 7M+4S.
6.34M for readdition with Z1=Z2: 5M+2S after 5M+2S.
5.34M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
5.35M for doubling: 2M+5S.
4.35M for doubling with Z1=1: 1M+5S.
11.7M for tripling: 5M+10S.
103.67M for scaling: 1I+3M+1S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition 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 + 2^³	8M + 5S + 1^³
addition		10M + 5S + 3^³	10M + 4S + 2^³
addition		10M + 5S + 4^³	10M + 4S + 3^³
doubling	Z1=1	1M + 5S
doubling		2M + 5S
doubling		1M + 7S
doubling		1M + 8S + 1*a
doubling		3M + 6S + 1*a
doubling	half*2=1	3M + 6S + 1half + 1a
doubling		3M + 3S + 2^⁴ + 1*a
doubling		3M + 3S + 2^⁴ + 1*a
tripling		5M + 10S + 1*a
tripling		8M + 7S + 1*a
tripling		9M + 5S + 1^³ + 2^⁴ + 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^²
      I = 4*HH
      J = H*I
      r = 2*(Y2-Y1)
      V = X1*I
      X3 = r^²-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)^²
      B = X1*A
      C = X2*A
      D = (Y2-Y1)^²
      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^²
      U2 = X2*Z1Z1
      S2 = Y2*Z1*Z1Z1
      H = U2-X1
      HH = H^²
      I = 4*HH
      J = H*I
      r = 2*(S2-Y1)
      V = X1*I
      X3 = r^²-J-2*V
      Y3 = r*(V-X3)-2*Y1*J
      Z3 = (Z1+H)^²-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^²
      T2 = T1*Z1
      T1 = T1*X2
      T2 = T2*Y2
      T1 = T1-X1
      T2 = T2-Y1
      Z3 = Z1*T1
      T3 = T1^²
      T4 = T3*T1
      T3 = T3*X1
      T1 = 2*T3
      X3 = T2^²
      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^²
      T2 = T1*Z1
      T1 = T1*X2
      T2 = T2*Y2
      T1 = X1-T1
      T2 = T2-Y1
      Z3 = Z1*T1
      T4 = T1^²
      T1 = T1*T4
      T4 = T4*X1
      X3 = T2^²
      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^²
      U2 = X2*Z1Z1
      S2 = Y2*Z1*Z1Z1
      H = U2-X1
      I = (2*H)^²
      J = H*I
      r = 2*(S2-Y1)
      V = X1*I
      X3 = r^²-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^²
      Z2Z2 = Z2^²
      U1 = X1*Z2Z2
      U2 = X2*Z1Z1
      S1 = Y1*Z2*Z2Z2
      S2 = Y2*Z1*Z1Z1
      H = U2-U1
      I = (2*H)^²
      J = H*I
      r = 2*(S2-S1)
      V = U1*I
      X3 = r^²-J-2*V
      Y3 = r*(V-X3)-2*S1*J
      Z3 = ((Z1+Z2)^²-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^²
      Z2Z2 = Z2^²
      U1 = X1*Z2Z2
      U2 = X2*Z1Z1
      S1 = Y1*Z2*Z2Z2
      S2 = Y2*Z1*Z1Z1
      H = U2-U1
      HH = H^²
      HHH = H*HH
      r = S2-S1
      V = U1*HH
      X3 = r^²-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^²
      ZZZ1 = Z1*ZZ1
      ZZ2 = Z2^²
      ZZZ2 = Z2*ZZ2
      A = X1*ZZ2
      B = X2*ZZ1-A
      c = Y1*ZZZ2
      d = Y2*ZZZ1-c
      e = B^²
      f = B*e
      g = A*e
      h = Z1*Z2
      f2g = 2*g+f
      X3 = d^²-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^²
      R1 = R1*R7
      R7 = R6*R7
      R2 = R2*R7
      R7 = R3^²
      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^²
      R8 = R8*R1
      R7 = R7*R1
      R1 = R2^²
      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 + 2^³ + 7add + 1*2 + 1*3.
Cost: 8M + 5S + 1^³ + 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^²
      U2 = X2*Z1^²
      S1 = Y1*Z2^³
      S2 = Y2*Z1^³
      P = U2-U1
      R = S2-S1
      X3 = R^²-(U1+U2)*P^²
      Y3 = (R*(-2*R^²+3*P^²*(U1+U2))-P^³*(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 + 3^³ + 6add.
Cost: 10M + 4S + 2^³ + 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^²
      U2 = X2*Z1^²
      S1 = Y1*Z2^³
      S2 = Y2*Z1^³
      P = U2-U1
      R = S2-S1
      X3 = R^²-(U1+U2)*P^²
      Y3 = R*(U1*P^²-X3)-S1*P^³
      Z3 = Z1*Z2*P

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

Cost: 10M + 5S + 4^³ + 6add + 1*2.
Cost: 10M + 4S + 3^³ + 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^²
      U2 = X2*Z1^²
      S1 = Y1*Z2^³
      S2 = Y2*Z1^³
      H = U2-U1
      r = S2-S1
      X3 = r^²-H^³-2*U1*H^²
      Y3 = r*(U1*H^²-X3)-S1*H^³
      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^²
      YY = Y1^²
      YYYY = YY^²
      S = 2*((X1+YY)^²-XX-YYYY)
      M = 3*XX+a
      T = M^²-2*S
      X3 = T
      Y3 = M*(S-T)-8*YYYY
      Z3 = 2*Y1

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

Cost: 2M + 5S + 6add + 3*2 + 1*3 + 1*8.
Source: 2009.04.01 Lange.

Explicit formulas:

      A = X1^²
      B = Y1^²
      C = B^²
      D = 2*((X1+B)^²-A-C)
      E = 3*A
      F = E^²
      X3 = F-2*D
      Y3 = E*(D-X3)-8*C
      Z3 = 2*Y1*Z1

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

Cost: 1M + 7S + 9add + 2*2 + 1*3 + 1*8.
Source: 2009.04.01 Arene–Lange–Naehrig–Ritzenthaler.

Explicit formulas:

      A = X1^²
      B = Y1^²
      ZZ = Z1^²
      C = B^²
      D = 2*((X1+B)^²-A-C)
      E = 3*A
      F = E^²
      X3 = F-2*D
      Y3 = E*(D-X3)-8*C
      Z3 = (Y1+Z1)^²-B-ZZ

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^²
      YY = Y1^²
      YYYY = YY^²
      ZZ = Z1^²
      S = 2*((X1+YY)^²-XX-YYYY)
      M = 3*XX+a*ZZ^²
      T = M^²-2*S
      X3 = T
      Y3 = M*(S-T)-8*YYYY
      Z3 = (Y1+Z1)^²-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^²
      YY = Y1^²
      ZZ = Z1^²
      S = 4*X1*YY
      M = 3*XX+a*ZZ^²
      T = M^²-2*S
      X3 = T
      Y3 = M*(S-T)-8*YY^²
      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^²
      R3 = R2*R3
      R3 = 2*R3
      R4 = R4^²
      R4 = a*R4
      R5 = R1^²
      R4 = R4+R5
      R5 = 2*R5
      R4 = R4+R5
      R2 = 2*R2
      R2 = R2^²
      R5 = R2^²
      R5 = half*R5
      R2 = R2*R1
      R1 = R4^²
      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" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 3M + 3S + 2^⁴ + 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^²
      M = 3*X1^²+a*Z1^⁴
      T = M^²-2*S
      X3 = T
      Y3 = M*(S-T)-8*Y1^⁴
      Z3 = 2*Y1*Z1

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

Cost: 3M + 3S + 2^⁴ + 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^²
      M = 3*X1^²+a*Z1^⁴
      T = M^²-2*S
      X3 = T
      Y3 = M*(S-T)-8*Y1^⁴
      Z3 = 2*Y1*Z1

Explicit formulas for tripling

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^²
      YY = Y1^²
      ZZ = Z1^²
      YYYY = YY^²
      M = 3*XX+a*ZZ^²
      MM = M^²
      E = 6*((X1+YY)^²-XX-YYYY)-MM
      EE = E^²
      T = 16*YYYY
      U = (M+E)^²-MM-EE-T
      X3 = 4*(X1*EE-4*YY*U)
      Y3 = 8*Y1*(U*(T-U)-E*EE)
      Z3 = (Z1+E)^²-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^²
      YY = Y1^²
      C = 2*YY
      M = 3*X1^²+a*ZZ^²
      E = 6*X1*C-M^²
      EE = E^²
      T = 2*C^²
      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 + 1^³ + 2^⁴ + 1*a + 7add + 1*2 + 1*3 + 1*4 + 2*8 + 1*12.
Source: 2005 Dimitrov–Imbert–Mishra.

Explicit formulas:

      M = 3*X1^²+a*Z1^⁴
      E = 12*X1*Y1^²-M^²
      T = 8*Y1^⁴
      X3 = 8*Y1^²*(T-M*E)+X1*E^²
      Y3 = Y1*(4*(M*E-T)*(2*T-M*E)-E^³)
      Z3 = Z1*E

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

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^²
      X3 = X1*AA
      Y3 = Y1*AA*A
      Z3 = 1