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

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

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

  y^²=x^³+3*a*(x+1)^²

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

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

Best operation counts

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

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

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

15.8M for addition: 11M+6S.
10.2M for addition with Z2=1: 7M+4S.
5.6M for addition with Z1=1 and Z2=1: 4M+2S.
14.8M for readdition: 10M+6S after 11M+6S.
10.2M for readdition with Z2=1: 7M+4S after 7M+4S.
5.6M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
7.6M for doubling: 2M+7S.
5M for doubling with Z1=1: 1M+5S.
10.8M for tripling: 6M+6S.
103.8M for scaling: 1I+3M+1S.

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

15.02M for addition: 11M+6S.
9.68M for addition with Z2=1: 7M+4S.
5.34M for addition with Z1=1 and Z2=1: 4M+2S.
14.02M for readdition: 10M+6S after 11M+6S.
9.68M for readdition with Z2=1: 7M+4S after 7M+4S.
5.34M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
6.69M for doubling: 2M+7S.
4.35M for doubling with Z1=1: 1M+5S.
10.02M for tripling: 6M+6S.
103.67M for scaling: 1I+3M+1S.

Summary of all explicit formulas

Operation	Assumptions	Cost	Readdition cost
addition	a3=3*a and Z1=1 and Z2=1	4M + 2S + 1*a3	4M + 2S + 1*a3
addition	a3=3*a and Z1=1 and Z2=1	4M + 3S + 1*a3	4M + 3S + 1*a3
addition	a3=3*a and Z2=1	7M + 4S + 1*a3	7M + 4S + 1*a3
addition	a3=3*a and Z2=1	8M + 3S + 1*a3	8M + 3S + 1*a3
addition	a3=3*a	11M + 6S + 1*a3	10M + 6S + 1*a3
addition	a3=3*a	13M + 4S + 1*a3	12M + 4S + 1*a3
addition		15M + 11S + 5^³ + 1*a	15M + 7S + 3^³ + 1*a
addition		7I + 11M + 9S + 5^³ + 1*a	5I + 9M + 8S + 4^³ + 1*a
doubling	a2=2a and a3=3a and Z1=1	1M + 5S + 1a2 + 1a3
doubling	a2=2a and a3=3a	2M + 7S + 1a2 + 1a3
doubling	a3=3*a	4M + 5S + 1a3 + 1a
doubling	a3=3*a	4M + 5S + 1^⁴ + 1a3 + 2a
tripling		6M + 6S + 2*a
tripling	b=4a-9 and c=-3a	6M + 7S + 1a + 1b + 1*c
scaling		1I + 3M + 1S

Explicit formulas for addition

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

Assumptions: a3=3*a and Z1=1 and Z2=1.
Cost: 4M + 2S + 1*a3 + 7add + 4*2 + 1*4.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

      C = X1-X2
      D = 2*(Y1-Y2)
      F = C^²
      F4 = 4*F
      Z3 = 2*C
      G = C*F4
      H = X2*F4
      X3 = D^²-G-2*H-a3*F4
      Y3 = D*(H-X3)-2*Y2*G
      ZZ3 = F4

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

Assumptions: a3=3*a and Z1=1 and Z2=1.
Cost: 4M + 3S + 1*a3 + 7add + 1*2.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 199, top display, plus Z2=1.

Explicit formulas:

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

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

Assumptions: a3=3*a and Z2=1.
Cost: 7M + 4S + 1*a3 + 10add + 3*2 + 1*4.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

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

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

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

Explicit formulas:

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

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

Assumptions: a3=3*a.
Cost: 11M + 6S + 1*a3 + 13add + 2*2 + 1*8 + 1*16.
Cost: 10M + 6S + 1*a3 + 13add + 2*2 + 1*8 + 1*16 dependent upon the first point.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

      ZZZ2 = Z2*ZZ2
      ZZZ1 = Z1*ZZ1
      A = X2*ZZ1-X1*ZZ2
      B = Y2*ZZZ1-Y1*ZZZ2
      AA = A^²
      C = (Z2+A)^²-ZZ2-AA
      CC = C^²
      CC8 = 8*CC
      D = X1*CC8
      Z3 = (Z1+C)^²-ZZ1-CC
      E = Z3^²
      X3 = 16*(B^²-A*AA)-D-a3*E
      Y3 = 2*B*(D-2*X3)-Y1*C*CC8
      ZZ3 = E

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

Assumptions: a3=3*a.
Cost: 13M + 4S + 1*a3 + 7add + 1*2.
Cost: 12M + 4S + 1*a3 + 7add + 1*2 dependent upon the first point.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 199, top display, plus Z2=1, plus simplification, plus projectification, plus denominator clearing, plus common-subexpression elimination.

Explicit formulas:

      A = X2*ZZ1-X1*ZZ2
      B = Y2*Z1*ZZ1-Y1*Z2*ZZ2
      C = Z2*A
      CC = C^²
      D = X1*CC
      Z3 = Z1*C
      E = Z3^²
      X3 = B^²-A*A^²-a3*E-2*D
      Y3 = B*(D-X3)-Y1*C*CC
      ZZ3 = E

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

Cost: 15M + 11S + 5^³ + 1*a + 7add + 1*2 + 1*3.
Cost: 15M + 7S + 3^³ + 1*a + 7add + 1*2 + 1*3 dependent upon the first point.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 199, top display, plus Z2=1, plus simplification, plus projectification, plus denominator clearing.

Explicit formulas:

      A = X2*Z1^²-X1*Z2^²
      B = Y2*Z1^³-Y1*Z2^³
      X3 = B^²-A^³-Z1^²*Z2^²*3*a*A^²-Z2^²*2*A^²*X1
      Y3 = B*(Z2^²*A^²*X1-X3)-Z2^³*A^³*Y1
      Z3 = Z1*Z2*A
      ZZ3 = Z3^²

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

Cost: 7I + 11M + 9S + 5^³ + 1*a + 7add + 1*2 + 1*3.
Cost: 5I + 9M + 8S + 4^³ + 1*a + 7add + 1*2 + 1*3 dependent upon the first point.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 199, top display, plus Z2=1, plus simplification, plus projectification.

Explicit formulas:

      D = Y2/Z2^³-Y1/Z1^³
      Z3 = X2/Z2^²-X1/Z1^²
      X3 = D^²-Z3^³-3*a*Z3^²-2*Z3^²*X1/Z1^²
      Y3 = D*(Z3^²*X1/Z1^²-X3)-Z3^³*Y1/Z1^³
      ZZ3 = Z3^²

Explicit formulas for doubling

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

Assumptions: a2=2*a and a3=3*a and Z1=1.
Cost: 1M + 5S + 1*a2 + 1*a3 + 9add + 3*2 + 1*3 + 1*4 + 1*8.

Explicit formulas:

      A = X1^²
      B = a2*(X1+1)
      C = 3*(A+B)
      D = Y1^²
      E = D^²
      Z3 = 2*Y1
      ZZ3 = 4*D
      F = 2*((X1+D)^²-A-E)
      X3 = C^²-a3*ZZ3-2*F
      Y3 = C*(F-X3)-8*E

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

Assumptions: a2=2*a and a3=3*a.
Cost: 2M + 7S + 1*a2 + 1*a3 + 12add + 2*2 + 1*3 + 1*8.
Source: 2007 Bernstein–Birkner–Lange–Peters.

Explicit formulas:

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

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

Assumptions: a3=3*a.
Cost: 4M + 5S + 1*a3 + 1*a + 6add + 2*2 + 1*3 + 1*4 + 1*6 + 1*8.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 198, bottom display, plus correction from 2007 Bernstein–Birkner–Lange–Peters to incorporate the missing -3a term, plus elimination of unused C, plus common-subexpression elimination.

Explicit formulas:

      YY1 = Y1^²
      A = Y1*Z1
      Z3 = 2*A
      B = 4*YY1*X1
      ZZ3 = Z3^²
      D = 3*X1^²
      E = D+6*a*ZZ1*(ZZ1+X1)
      X3 = E^²-2*B-a3*ZZ3
      Y3 = E*(B-X3)-8*YY1^²

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

Assumptions: a3=3*a.
Cost: 4M + 5S + 1^⁴ + 1*a3 + 2*a + 7add + 2*2 + 1*3 + 2*4 + 2*6 + 1*8.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 198, bottom display, plus correction from 2007 Bernstein–Birkner–Lange–Peters to incorporate the missing -3a term.

Explicit formulas:

      A = Y1*Z1
      Z3 = 2*A
      B = 4*Y1^²*X1
      C = B+6*a*A^²
      ZZ3 = 4*A^²
      D = 3*X1^²
      E = D+6*a*ZZ1*(ZZ1+X1)
      X3 = E^²-2*B-a3*ZZ3
      Y3 = E*(B-X3)-8*Y1^⁴

Explicit formulas for tripling

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

Cost: 6M + 6S + 2*a + 7add + 4*3 + 2*4 + 1*9.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 198, middle display, plus common-subexpression elimination.

Explicit formulas:

      YY1 = Y1^²
      A = (X1+3*ZZ1)^²
      B = a*ZZ1*A
      Xt = YY1+B
      Yt = Y1*(YY1-3*B)
      Zt = X1*Z1
      C = Zt^²
      Ca = a*C
      E = 3*Ca*(4*Ca-9*C-Xt)^²
      X3 = Yt^²-E
      Y3 = Yt*(X3+4*E)
      Z3 = 3*Xt*Zt
      ZZ3 = Z3^²

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

Assumptions: b=4*a-9 and c=-3*a.
Cost: 6M + 7S + 1*a + 1*b + 1*c + 6add + 3*3 + 1*4.
Source: 2006 Doche–Icart–Kohel "Efficient scalar multiplication by isogeny decompositions", page 198, middle display.

Explicit formulas:

      A = (X1+3*ZZ1)^²
      B = a*ZZ1*A
      Xt = Y1^²+B
      Yt = Y1*(Y1^²-3*B)
      Zt = X1*Z1
      C = Zt^²
      D = (b*C-Xt)^²
      E = c*C*D
      X3 = (Yt^²+E)
      Y3 = Yt*(X3-4*E)
      Z3 = 3*Xt*Zt
      ZZ3 = Z3^²

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
      ZZ3 = 1