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^2=x^3+3*a*(x+1)^2
```

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

```  x=X/Z^2
y=Y/Z^3
ZZ=Z^2
```

## 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

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 + 53 + 1*a 15M + 7S + 33 + 1*a
addition 7I + 11M + 9S + 53 + 1*a 5I + 9M + 8S + 43 + 1*a
doubling a2=2*a and a3=3*a and Z1=1 1M + 5S + 1*a2 + 1*a3
doubling a2=2*a and a3=3*a 2M + 7S + 1*a2 + 1*a3
doubling a3=3*a 4M + 5S + 1*a3 + 1*a
doubling a3=3*a 4M + 5S + 14 + 1*a3 + 2*a
tripling 6M + 6S + 2*a
tripling b=4*a-9 and c=-3*a 6M + 7S + 1*a + 1*b + 1*c
scaling 1I + 3M + 1S

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^2
F4 = 4*F
Z3 = 2*C
G = C*F4
H = X2*F4
X3 = D^2-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^2
F = C^2
G = C*F
H = A*F
X3 = D^2-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^2
F4 = 4*F
Z3 = (Z1+C)^2-ZZ1-F
E = Z3^2
G = C*F4
H = A*F4
X3 = D^2-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^2
F = C^2
G = C*F
H = A*F
X3 = D^2-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^2
C = (Z2+A)^2-ZZ2-AA
CC = C^2
CC8 = 8*CC
D = X1*CC8
Z3 = (Z1+C)^2-ZZ1-CC
E = Z3^2
X3 = 16*(B^2-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^2
D = X1*CC
Z3 = Z1*C
E = Z3^2
X3 = B^2-A*A^2-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 + 53 + 1*a + 7add + 1*2 + 1*3.
• Cost: 15M + 7S + 33 + 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^2-X1*Z2^2
B = Y2*Z1^3-Y1*Z2^3
X3 = B^2-A^3-Z1^2*Z2^2*3*a*A^2-Z2^2*2*A^2*X1
Y3 = B*(Z2^2*A^2*X1-X3)-Z2^3*A^3*Y1
Z3 = Z1*Z2*A
ZZ3 = Z3^2
```

The "add-2006-dik" addition formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Cost: 7I + 11M + 9S + 53 + 1*a + 7add + 1*2 + 1*3.
• Cost: 5I + 9M + 8S + 43 + 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^3-Y1/Z1^3
Z3 = X2/Z2^2-X1/Z1^2
X3 = D^2-Z3^3-3*a*Z3^2-2*Z3^2*X1/Z1^2
Y3 = D*(Z3^2*X1/Z1^2-X3)-Z3^3*Y1/Z1^3
ZZ3 = Z3^2
```

## 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^2
B = a2*(X1+1)
C = 3*(A+B)
D = Y1^2
E = D^2
Z3 = 2*Y1
ZZ3 = 4*D
F = 2*((X1+D)^2-A-E)
X3 = C^2-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^2
B = a2*ZZ1*(X1+ZZ1)
C = 3*(A+B)
D = Y1^2
E = D^2
Z3 = (Y1+Z1)^2-D-ZZ1
ZZ3 = Z3^2
F = 2*((X1+D)^2-A-E)
X3 = C^2-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^2
A = Y1*Z1
Z3 = 2*A
B = 4*YY1*X1
ZZ3 = Z3^2
D = 3*X1^2
E = D+6*a*ZZ1*(ZZ1+X1)
X3 = E^2-2*B-a3*ZZ3
Y3 = E*(B-X3)-8*YY1^2
```

The "dbl-2006-dik" doubling formulas [database entry; Sage verification script; Sage output; three-operand code]:
• Assumptions: a3=3*a.
• Cost: 4M + 5S + 14 + 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^2*X1
C = B+6*a*A^2
ZZ3 = 4*A^2
D = 3*X1^2
E = D+6*a*ZZ1*(ZZ1+X1)
X3 = E^2-2*B-a3*ZZ3
Y3 = E*(B-X3)-8*Y1^4
```

## 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^2
A = (X1+3*ZZ1)^2
B = a*ZZ1*A
Xt = YY1+B
Yt = Y1*(YY1-3*B)
Zt = X1*Z1
C = Zt^2
Ca = a*C
E = 3*Ca*(4*Ca-9*C-Xt)^2
X3 = Yt^2-E
Y3 = Yt*(X3+4*E)
Z3 = 3*Xt*Zt
ZZ3 = Z3^2
```

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)^2
B = a*ZZ1*A
Xt = Y1^2+B
Yt = Y1*(Y1^2-3*B)
Zt = X1*Z1
C = Zt^2
D = (b*C-Xt)^2
E = c*C*D
X3 = (Yt^2+E)
Y3 = Yt*(X3-4*E)
Z3 = 3*Xt*Zt
ZZ3 = Z3^2
```

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