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:
y2=x3+3*a*(x+1)2

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

x=X/Z2
y=Y/Z3
ZZ=Z2

## 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 = C2
F4 = 4*F
Z3 = 2*C
G = C*F4
H = X2*F4
X3 = D2-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 = Z32
F = C2
G = C*F
H = A*F
X3 = D2-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 = C2
F4 = 4*F
Z3 = (Z1+C)2-ZZ1-F
E = Z32
G = C*F4
H = A*F4
X3 = D2-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 = Z32
F = C2
G = C*F
H = A*F
X3 = D2-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 = A2
C = (Z2+A)2-ZZ2-AA
CC = C2
CC8 = 8*CC
D = X1*CC8
Z3 = (Z1+C)2-ZZ1-CC
E = Z32
X3 = 16*(B2-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 = C2
D = X1*CC
Z3 = Z1*C
E = Z32
X3 = B2-A*A2-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*Z12-X1*Z22
B = Y2*Z13-Y1*Z23
X3 = B2-A3-Z12*Z22*3*a*A2-Z22*2*A2*X1
Y3 = B*(Z22*A2*X1-X3)-Z23*A3*Y1
Z3 = Z1*Z2*A
ZZ3 = Z32

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/Z23-Y1/Z13
Z3 = X2/Z22-X1/Z12
X3 = D2-Z33-3*a*Z32-2*Z32*X1/Z12
Y3 = D*(Z32*X1/Z12-X3)-Z33*Y1/Z13
ZZ3 = Z32

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

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*Y12*X1
C = B+6*a*A2
ZZ3 = 4*A2
D = 3*X12
E = D+6*a*ZZ1*(ZZ1+X1)
X3 = E2-2*B-a3*ZZ3
Y3 = E*(B-X3)-8*Y14

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

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 = Y12+B
Yt = Y1*(Y12-3*B)
Zt = X1*Z1
C = Zt2
D = (b*C-Xt)2
E = c*C*D
X3 = (Yt2+E)
Y3 = Yt*(X3-4*E)
Z3 = 3*Xt*Zt
ZZ3 = Z32

## 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 = A2
X3 = X1*AA
Y3 = Y1*AA*A
Z3 = 1
ZZ3 = 1