Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Short Weierstrass curves EFD / Genus-1 large-characteristic / Modified Jacobian coordinates for short Weierstrass curves

Modified Jacobian coordinates 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

Modified Jacobian coordinates [database entry] represent x y as X Y Z T satisfying the following equations:

  x=X/Z^²
  y=Y/Z^³
  T=a*Z^⁴

Best operation counts

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

18M for addition: 11M+7S. 12M+6S.
13M for addition with Z2=1: 7M+6S.
7M for addition with Z1=1 and Z2=1: 3M+4S.
16M for readdition: 10M+6S after 11M+7S. 11M+5S after 12M+6S.
13M for readdition with Z2=1: 7M+6S after 7M+6S.
7M for readdition with Z1=1 and Z2=1: 3M+4S after 3M+4S.
8M for doubling: 3M+5S. 4M+4S.
7M for doubling with Z1=1: 2M+5S.

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

16.6M for addition: 11M+7S.
11.8M for addition with Z2=1: 7M+6S.
6.2M for addition with Z1=1 and Z2=1: 3M+4S.
14.8M for readdition: 10M+6S after 11M+7S.
11.8M for readdition with Z2=1: 7M+6S after 7M+6S.
6.2M for readdition with Z1=1 and Z2=1: 3M+4S after 3M+4S.
7M for doubling: 3M+5S.
6M for doubling with Z1=1: 2M+5S.

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

15.69M for addition: 11M+7S.
11.02M for addition with Z2=1: 7M+6S.
5.68M for addition with Z1=1 and Z2=1: 3M+4S.
14.02M for readdition: 10M+6S after 11M+7S.
11.02M for readdition with Z2=1: 7M+6S after 7M+6S.
5.68M for readdition with Z1=1 and Z2=1: 3M+4S after 3M+4S.
6.35M for doubling: 3M+5S.
5.35M for doubling with Z1=1: 2M+5S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	3M + 4S + 1*a	3M + 4S + 1*a
addition	Z2=1	7M + 6S + 1*a	7M + 6S + 1*a
addition		11M + 7S + 1*a	10M + 6S + 1*a
addition		12M + 6S + 1*a	11M + 5S + 1*a
doubling	Z1=1	2M + 5S
doubling		3M + 5S
doubling		4M + 4S

Explicit formulas for addition

The "mmadd-2009-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z1=1 and Z2=1.
Cost: 3M + 4S + 1*a + 9add + 5*2 + 1*4 + 1*16.
Source: 2009.04.27 Bernstein–Lange.

Explicit formulas:

      H = X2-X1
      HH = H^²
      HHHH = HH^²
      Z3 = 2*H
      ZZ3 = 4*HH
      J = 2*((H+HH)^²-HH-HHHH)
      r = 2*(Y2-Y1)
      V = X1*ZZ3
      X3 = r^²-J-2*V
      Y3 = r*(V-X3)-2*Y1*J
      T3 = 16*a*HHHH

The "madd-2009-bl" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Assumptions: Z2=1.
Cost: 7M + 6S + 1*a + 9add + 3*2 + 1*4.
Source: 2009.04.27 Bernstein–Lange.

Explicit formulas:

      ZZ1 = Z1^²
      H = X2*ZZ1-X1
      HH = H^²
      I = 4*HH
      J = H*I
      r = 2*(Y2*Z1*ZZ1-Y1)
      V = X1*I
      X3 = r^²-J-2*V
      Y3 = r*(V-X3)-2*Y1*J
      Z3 = (Z1+H)^²-ZZ1-HH
      ZZ3 = Z3^²
      T3 = a*ZZ3^²

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

Cost: 11M + 7S + 1*a + 9add + 4*2.
Cost: 10M + 6S + 1*a + 9add + 4*2 dependent upon the first point.
Source: 2009.04.01 Bernstein–Lange.

Explicit formulas:

      ZZ1 = Z1^²
      ZZ2 = Z2^²
      U1 = X1*ZZ2
      U2 = X2*ZZ1
      S1 = Y1*Z2*ZZ2
      S2 = Y2*Z1*ZZ1
      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)^²-ZZ1-ZZ2)*H
      ZZ3 = Z3^²
      T3 = a*ZZ3^²

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

Cost: 12M + 6S + 1*a + 6add + 1*2.
Cost: 11M + 5S + 1*a + 6add + 1*2 dependent upon the first point.
Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (9), plus common-subexpression elimination.

Explicit formulas:

      ZZ1 = Z1^²
      ZZ2 = Z2^²
      U1 = X1*ZZ2
      U2 = X2*ZZ1
      S1 = Y1*Z2*ZZ2
      S2 = Y2*Z1*ZZ1
      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
      ZZ3 = Z3^²
      T3 = a*ZZ3^²

Explicit formulas for doubling

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

Assumptions: Z1=1.
Cost: 2M + 5S + 7add + 5*2 + 1*3.
Source: 2009.04.27 Bernstein–Lange.

Explicit formulas:

      XX = X1^²
      A = 2*Y1^²
      AA = A^²
      U = 2*AA
      S = (X1+A)^²-XX-AA
      M = 3*XX+T1
      X3 = M^²-2*S
      Y3 = M*(S-X3)-U
      Z3 = 2*Y1
      T3 = 2*U*T1

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

Cost: 3M + 5S + 7add + 5*2 + 1*3.
Source: 2009.04.01 Bernstein–Lange.

Explicit formulas:

      XX = X1^²
      A = 2*Y1^²
      AA = A^²
      U = 2*AA
      S = (X1+A)^²-XX-AA
      M = 3*XX+T1
      X3 = M^²-2*S
      Y3 = M*(S-X3)-U
      Z3 = 2*Y1*Z1
      T3 = 2*U*T1

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

Cost: 4M + 4S + 4add + 3*2 + 1*3 + 1*4 + 1*8.
Source: 1998 Cohen–Miyaji–Ono "Efficient elliptic curve exponentiation using mixed coordinates", formula (10), plus common-subexpression elimination.

Explicit formulas:

      XX = X1^²
      YY = Y1^²
      U = 8*YY^²
      S = 4*X1*YY
      M = 3*XX+T1
      X3 = M^²-2*S
      Y3 = M*(S-X3)-U
      Z3 = 2*Y1*Z1
      T3 = 2*U*T1

Modified Jacobian coordinates for short Weierstrass curves

Best operation counts

Summary of all explicit formulas

Explicit formulas for addition

Explicit formulas for doubling

Explicit formulas for tripling

Explicit formulas for differential addition

Explicit formulas for differential addition and doubling

Explicit formulas for scaling