Explicit-Formulas Database
Genus-1 curves over large-characteristic fields
Doubling-oriented Doche–Icart–Kohel curves EFD / Genus-1 large-characteristic / Standard coordinates for doubling-oriented Doche–Icart–Kohel curves

Standard coordinates for doubling-oriented Doche–Icart–Kohel curves

An elliptic curve in doubling-oriented Doche–Icart–Kohel form [more information] has parameters a and coordinates x y satisfying the following equations:

  y^²=x^³+a*x^²+16*a*x

Standard coordinates [database entry] represent x y as X Y Z ZZ satisfying the following equations:

  x=X/Z
  y=Y/ZZ
  ZZ=Z^²

Best operation counts

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

17M for addition: 12M+5S.
12M for addition with Z2=1: 8M+4S. 9M+3S.
8M for addition with Z1=1 and Z2=1: 4M+4S. 4M+4S.
17M for readdition: 12M+5S after 12M+5S.
12M for readdition with Z2=1: 8M+4S after 8M+4S. 9M+3S after 9M+3S.
8M for readdition with Z1=1 and Z2=1: 4M+4S after 4M+4S. 4M+4S after 4M+4S.
7M for doubling: 2M+5S. 3M+4S.
6M for doubling with Z1=1: 1M+5S.
103M for scaling: 1I+2M+1S.

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

16M for addition: 12M+5S.
11.2M for addition with Z2=1: 8M+4S.
7.2M for addition with Z1=1 and Z2=1: 4M+4S. 4M+4S.
16M for readdition: 12M+5S after 12M+5S.
11.2M for readdition with Z2=1: 8M+4S after 8M+4S.
7.2M for readdition with Z1=1 and Z2=1: 4M+4S after 4M+4S. 4M+4S after 4M+4S.
6M for doubling: 2M+5S.
5M for doubling with Z1=1: 1M+5S.
102.8M for scaling: 1I+2M+1S.

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

15.35M for addition: 12M+5S.
10.68M for addition with Z2=1: 8M+4S.
6.68M for addition with Z1=1 and Z2=1: 4M+4S. 4M+4S.
15.35M for readdition: 12M+5S after 12M+5S.
10.68M for readdition with Z2=1: 8M+4S after 8M+4S.
6.68M for readdition with Z1=1 and Z2=1: 4M+4S after 4M+4S. 4M+4S after 4M+4S.
5.35M for doubling: 2M+5S.
4.35M for doubling with Z1=1: 1M+5S.
102.67M for scaling: 1I+2M+1S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	Z1=1 and Z2=1	4M + 4S + 1*a	4M + 4S + 1*a
addition	Z1=1 and Z2=1	4M + 4S + 1*a	4M + 4S + 1*a
addition	Z1=1 and Z2=1	6M + 3S + 1*a	6M + 3S + 1*a
addition	Z2=1	8M + 4S + 1*a	8M + 4S + 1*a
addition	Z2=1	9M + 3S + 1*a	9M + 3S + 1*a
addition		12M + 5S + 1*a	12M + 5S + 1*a
addition		21M + 15S + 2^⁴ + 1*a	21M + 11S + 1^⁴ + 1*a
addition		7I + 12M + 9S + 1^⁴ + 1*a	4I + 9M + 8S + 1^⁴ + 1*a
doubling	a2=2a and a16=16a and Z1=1	1M + 5S + 1a2 + 1a
doubling	a2=2*a	2M + 5S + 1a2 + 1a
doubling	a4=4*a	3M + 4S + 1a + 1a4
doubling	a16=16*a	3M + 8S + 1a16 + 2a
scaling		1I + 2M + 1S

Explicit formulas for addition

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

Assumptions: Z1=1 and Z2=1.
Cost: 4M + 4S + 1*a + 10add + 2*2.

Explicit formulas:

      A = Y2-Y1
      AA = A^²
      B = X2-X1
      CC = B^²
      F = X1*CC
      Z3 = 2*CC
      D = X2*Z3
      ZZ3 = Z3^²
      X3 = 2*(AA-F)-a*Z3-D
      Y3 = ((A+B)^²-AA-CC)*(D-X3)-Y2*ZZ3

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

Assumptions: Z1=1 and Z2=1.
Cost: 4M + 4S + 1*a + 10add + 3*2.

Explicit formulas:

      A = Y2-Y1
      AA = A^²
      B = X2-X1
      CC = B^²
      D = 2*X2*CC
      F = X1*CC
      Z3 = 2*CC
      ZZ3 = Z3^²
      X3 = 2*(AA-F)-a*Z3-D
      Y3 = ((A+B)^²-AA-CC)*(D-X3)-Y2*ZZ3

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

Assumptions: Z1=1 and Z2=1.
Cost: 6M + 3S + 1*a + 7add.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 197, middle display, plus substitution Z2=1.

Explicit formulas:

      A = Y1-Y2
      B = X1-X2
      C = B
      Z3 = C^²
      D = X1*Z3
      E = A^²
      F = X2*B*C
      X3 = E-a*Z3-D-F
      G = Z3^²
      H = A*C
      Y3 = H*(D-X3)-Y1*G
      ZZ3 = G

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

Assumptions: Z2=1.
Cost: 8M + 4S + 1*a + 10add + 3*2.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      A = Y2*ZZ1-Y1
      AA = A^²
      B = X2*Z1-X1
      C = B*Z1
      CC = C^²
      D = 2*X2*CC
      F = X1*B*C
      Z3 = 2*CC
      ZZ3 = Z3^²
      X3 = 2*(AA-F)-a*Z3-D
      Y3 = ((A+C)^²-AA-CC)*(D-X3)-Y2*ZZ3

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

Assumptions: Z2=1.
Cost: 9M + 3S + 1*a + 7add.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 197, middle display, plus reversal of roles of 1 and 2.

Explicit formulas:

      A = Y2*ZZ1-Y1
      B = X2*Z1-X1
      C = B*Z1
      Z3 = C^²
      D = X2*Z3
      E = A^²
      F = X1*B*C
      X3 = E-a*Z3-D-F
      G = Z3^²
      H = A*C
      Y3 = H*(D-X3)-Y2*G
      ZZ3 = G

The "add-2006-dik-3" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:

Cost: 12M + 5S + 1*a + 10add + 4*2.
Source: 2007 Bernstein–Lange; derived from 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 197, middle display, by substitution Z2=1, simplification, projectification, clearing denominators, common-subexpression elimination.

Explicit formulas:

      A = Y1*ZZ2-Y2*ZZ1
      AA = A^²
      X2Z1 = X2*Z1
      B = X1*Z2-X2Z1
      C = B*Z2
      E = C*Z1
      EE = E^²
      F = E*C
      D = F*X1
      U = AA-a*EE-D-X2Z1*E*B
      X3 = 2*U
      Y3 = 2*((E+A)^²-EE-AA)*(D-U)-Y1*(2*F)^²
      Z3 = 2*EE
      ZZ3 = Z3^²

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

Cost: 21M + 15S + 2^⁴ + 1*a + 7add.
Cost: 21M + 11S + 1^⁴ + 1*a + 7add dependent upon the first point.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 197, middle display, plus substitution Z2=1, plus simplification, plus projectification, plus clearing denominators.

Explicit formulas:

      A = Y1*Z2^²-Y2*Z1^²
      B = X1*Z2-X2*Z1
      D = Z1*Z2^²*B^²*X1
      U = A^²-a*B^²*Z1^²*Z2^²-D-X2*B^²*Z1^²*Z2
      X3 = U
      Y3 = Z1*Z2*A*B*(D-U)-Z1^²*Z2^⁴*Y1*B^⁴
      Z3 = Z1^²*Z2^²*B^²
      ZZ3 = Z3^²

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

Cost: 7I + 12M + 9S + 1^⁴ + 1*a + 7add.
Cost: 4I + 9M + 8S + 1^⁴ + 1*a + 7add dependent upon the first point.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 197, middle display, plus substitution Z2=1, plus simplification, plus projectification.

Explicit formulas:

      A = Y1/Z1^²-Y2/Z2^²
      B = (X1/Z1)-(X2/Z2)
      D = (X1/Z1)*B^²
      X3 = A^²-a*B^²-D-(X2/Z2)*B^²
      Y3 = A*B*(D-X3)-(Y1/Z1^²)*B^⁴
      Z3 = B^²
      ZZ3 = Z3^²

Explicit formulas for doubling

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

Assumptions: a2=2*a and a16=16*a and Z1=1.
Cost: 1M + 5S + 1*a2 + 1*a + 7add + 2*2 + 1*64.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      A = X1^²
      B = A-a16
      C = a2*A
      YY = Y1^²
      YY2 = 2*YY
      Z3 = 2*YY2
      X3 = B^²
      V = (Y1+B)^²-YY-X3
      Y3 = V*(X3+64*C+a*(YY2-C))
      ZZ3 = Z3^²

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

Assumptions: a2=2*a.
Cost: 2M + 5S + 1*a2 + 1*a + 7add + 2*2 + 1*8 + 1*64.
Source: 2007 Bernstein–Lange.

Explicit formulas:

      A = X1^²
      U = a2*ZZ1
      B = A-8*U
      C = A*U
      YY = Y1^²
      YY2 = 2*YY
      Z3 = 2*YY2
      X3 = B^²
      V = (Y1+B)^²-YY-X3
      Y3 = V*(X3+64*C+a*(YY2-C))
      ZZ3 = Z3^²

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

Assumptions: a4=4*a.
Cost: 3M + 4S + 1*a + 1*a4 + 4add + 2*2 + 1*4 + 1*32.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 196, bottom display, plus elimination of common subexpressions.

Explicit formulas:

      A = X1^²
      U = a4*ZZ1
      B = A-4*U
      C = A*U
      Z3 = (2*Y1)^²
      X3 = B^²
      Y3 = Y1*B*(2*(X3+32*C)+a*(Z3-C))
      ZZ3 = Z3^²

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

Assumptions: a16=16*a.
Cost: 3M + 8S + 1*a16 + 2*a + 4add + 1*2 + 2*4 + 1*256.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 196, bottom display.

Explicit formulas:

      A = X1^²
      B = X1^²-a16*Z1^²
      YT = Y1*B
      X3 = B^²
      Z3 = 4*Y1^²
      C = X1^²*a*Z1^²
      D = Z3^²
      E = a*(Z3-4*C)
      Y3 = YT*(2*X3+E+256*C)
      ZZ3 = D

Explicit formulas for tripling

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 + 2M + 1S + 0add.

Explicit formulas:

      A = 1/Z1
      X3 = X1*A
      Y3 = Y1*A^²
      Z3 = 1
      ZZ3 = 1