Explicit-Formulas Database

# Genus-1 curves over large-characteristic fields

## Doubling-oriented Doche–Icart–Kohel curves: y^2=x^3+a*x^2+16*a*x

Standard coordinates: x=X/Z, y=Y/ZZ, ZZ=Z2

## Tripling-oriented Doche–Icart–Kohel curves: y^2=x^3+3*a*(x+1)^2

Standard coordinates: x=X/Z2, y=Y/Z3, ZZ=Z2

## Edwards curves: x^2+y^2=c^2*(1+d*x^2*y^2)

Inverted coordinates: x=Z/X, y=Z/Y
Projective coordinates: x=X/Z, y=Y/Z
YZ coordinates with square d: r*y=Y/Z, c=1, d=r2
Squared YZ coordinates with square d: r*y2=Y/Z, c=1, d=r2

## Hessian curves: x^3+y^3+1=3*d*x*y

Extended coordinates: x=X/Z, y=Y/Z, XX=X*X, YY=Y*Y, ZZ=Z*Z, XY=2*X*Y, XZ=2*X*Z, YZ=2*Y*Z
Projective coordinates: x=X/Z, y=Y/Z

## Jacobi intersections: s^2+c^2=1, a*s^2+d^2=1

Extended coordinates: s=S/Z, c=C/Z, d=D/Z, SC=S*C, DZ=D*Z
Projective coordinates: s=S/Z, c=C/Z, d=D/Z

## Jacobi quartics: y^2=x^4+2*a*x^2+1

Doubling-oriented XXYZZ coordinates: x=X/Z, y=Y/ZZ, XX=X2, ZZ=Z2, a2+c2=1
Doubling-oriented XXYZZR coordinates: x=X/Z, y=Y/ZZ, XX=X2, ZZ=Z2, R=2*X*Z, a2+c2=1
Doubling-oriented XYZ coordinates: x=X/Z, y=Y/Z2, a2+c2=1
XXYZZ coordinates: x=X/Z, y=Y/ZZ, XX=X2, ZZ=Z2
XXYZZR coordinates: x=X/Z, y=Y/ZZ, XX=X2, ZZ=Z2, R=2*X*Z
XYZ coordinates: x=X/Z, y=Y/Z2

## Montgomery curves: b*y^2=x^3+a*x^2+x

XZ coordinates: x=X/Z

## Short Weierstrass curves: y^2=x^3+a*x+b

Jacobian coordinates with a4=0: x=X/Z2, y=Y/Z3, a=0
Jacobian coordinates with a4=-3: x=X/Z2, y=Y/Z3, a=-3
Jacobian coordinates: x=X/Z2, y=Y/Z3
Modified Jacobian coordinates: x=X/Z2, y=Y/Z3, T=a*Z4
Projective coordinates with a4=-1: x=X/Z, y=Y/Z, a=-1
Projective coordinates with a4=-3: x=X/Z, y=Y/Z, a=-3
Projective coordinates: x=X/Z, y=Y/Z
W12 coordinates with a6=0: x=X/Z, y=Y/Z2, b=0
XYZZ coordinates with a4=-3: x=X/ZZ, y=Y/ZZZ, ZZ3=ZZZ2, a=-3
XYZZ coordinates: x=X/ZZ, y=Y/ZZZ, ZZ3=ZZZ2
XZ coordinates: x=X/Z

## Twisted Edwards curves: a*x^2+y^2=1+d*x^2*y^2

Extended coordinates with a=-1: x=X/Z, y=Y/Z, x*y=T/Z, a=-1
Extended coordinates: x=X/Z, y=Y/Z, x*y=T/Z
Inverted coordinates: x=Z/X, y=Z/Y
Projective coordinates: x=X/Z, y=Y/Z

## Twisted Hessian curves: a*x^3+y^3+1=d*x*y

Projective coordinates: x=X/Z, y=Y/Z

The EFD currently includes 454 explicit formulas for addition, doubling, tripling, and scaling of points in 33 representations on 10 shapes of genus-1 curves over large-characteristic fields.

## Speed tables

The following speed tables distinguish between eighteen different operations:
• DBL: Doubling. P1 |-> P1+P1.
• reADD: Readdition; i.e., addition of an input that has been added before, when all reusable intermediate results are cached. P1,P2 |-> P1+P2 when all results depending solely on P2 are cached. Classic example: typical formulas to compute (X1:Y1:Z1) + (X2:Y2:Z2) in Jacobian coordinates begin by computing Z12, Z13, Z22, and Z23; caching Z22 and Z23 saves 1M+1S in a readdition of (X2:Y2:Z2).
• mADD: Mixed addition; i.e., addition of an input that has been scaled to have Z-coordinate 1. P1,P2 |-> P1+P2 when Z(P2)=1.
• mDBL: Mixed doubling; i.e., doubling of an input that has been scaled to have Z-coordinate 1. P1 |-> P1+P1 when Z(P1)=1.
• mmADD: Addition of two inputs that have been scaled to have Z-coordinate 1. P1,P2 |-> P1+P2 when Z(P1)=1 and Z(P2)=1.
• mmreADD: Addition of two inputs that have been scaled to have Z-coordinate 1, where the second input has been added before.
• SUNI: Strongly unified addition; i.e., addition that also works without change for doubling.
• TPL: Tripling. P1 |-> P1+P1+P1.
• mDADD: Mixed differential addition, i.e., addition of points whose difference is known and whose difference has Z-coordinate 1. P3-P2,P2,P3 |-> P3+P2 when Z(P3-P2)=1.
• LADD: A ladder step; i.e., a differential addition and a doubling of one summand. P3-P2,P2,P3 |-> P2+P2,P3+P2.
• mLADD: A mixed ladder step; i.e., a mixed differential addition and a doubling of one summand. P3-P2,P2,P3 |-> P2+P2,P3+P2 when Z(P3-P2)=1.
• SCALE: Scaling to have Z-coordinate 1.
The tables are sorted in decreasing order of DBL cost; ties are broken in decreasing order of ADD cost; ties are broken in decreasing order of reADD cost; etc.

Smallest multiplication counts assuming I=100M, S=1M, *param=0M, add=0M, *const=0M:
Short Weierstrass, projective 11 14 14 14 11 11 11 8 7 7 7 17 102
Short Weierstrass, projective with a4=-1 11 14 14 14 11 11 11 8 7 7 7 16 102
Short Weierstrass, projective with a4=-3 10 14 14 14 11 11 11 8 7 7 7 17 102
Short Weierstrass, XYZZ 10 14 14 14 10 10 10 7 6 6 6 104
Tripling-oriented Doche–Icart–Kohel, standard 9 17 16 17 11 11 11 6 6 6 6 12 104
Short Weierstrass, Jacobian 9 16 14 16 11 11 11 6 6 6 6 15 104
Short Weierstrass, XYZZ with a4=-3 9 14 14 14 10 10 10 7 6 6 6 104
Hessian, extended 9 12 12 12 11 11 11 9 11 11 11 105
Short Weierstrass, modified Jacobian 8 18 16 18 13 13 13 7 7 7 7
Short Weierstrass, Jacobian with a4=-3 8 16 14 16 11 11 11 6 6 6 6 14 104
Jacobi quartic, XYZ 8 13 11 14 11 11 11 5 7 7 7 13 103
Jacobi quartic, doubling-oriented XYZ 8 13 11 14 11 11 11 5 7 7 7 13 103
Twisted Hessian, projective 8 12 12 12 12 12 12 8 12 12 12 12 14
Hessian, projective 8 12 12 12 10 10 10 6 8 7 8 12 14 102
Twisted Edwards, extended 8 9 9 9 8 8 8 7 7 7 7 9 14
Twisted Edwards, extended with a=-1 8 8 8 8 7 7 7 7 6 6 6 8 14
Doubling-oriented Doche–Icart–Kohel, standard 7 17 17 17 12 12 12 6 8 8 8 103
Short Weierstrass, W12 with a6=0 7 17 16 17 13 13 13 7 13 13 13
Short Weierstrass, Jacobian with a4=0 7 16 14 16 11 11 11 6 6 6 6 15 104
Jacobi intersection, projective 7 14 12 14 12 11 12 6 10 9 10 14 14 103
Jacobi intersection, extended 7 12 12 12 11 11 11 7 11 11 11 12 16 104
Twisted Edwards, projective 7 11 11 11 10 10 10 6 7 7 7 11 12
Edwards, projective 7 11 11 11 9 9 9 6 7 7 7 11 13 102
Jacobi quartic, XXYZZ 7 11 10 11 9 9 9 6 9 9 9 11 14 104
Jacobi quartic, doubling-oriented XXYZZ 7 11 10 11 9 9 9 6 9 9 9 11 14 104
Jacobi quartic, doubling-oriented XXYZZR 7 10 10 10 9 9 9 7 9 9 9 10 15 103
Jacobi quartic, XXYZZR 7 10 10 10 9 9 9 7 9 9 9 10 15 103
Edwards, inverted 7 10 10 10 9 9 9 6 7 7 7 10 13 102
Twisted Edwards, inverted 7 10 10 10 9 9 9 6 7 7 7 10
Short Weierstrass, XZ 7 7 9 8 16 15
Montgomery, XZ 4 3 6 5 10 9 101
Edwards, squared YZ with square d 4 3 6 5 10 9 101
Edwards, YZ with square d 4 2 8 7 10 9 101

Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:
Short Weierstrass, projective 9.8 13.6 13.6 13.6 10.6 10.6 10.6 7.0 6.6 6.6 6.6 15.8 102.0
Short Weierstrass, projective with a4=-1 9.8 13.6 13.6 13.6 10.6 10.6 10.6 7.0 6.6 6.6 6.6 15.4 102.0
Short Weierstrass, projective with a4=-3 9.4 13.6 13.6 13.6 10.6 10.6 10.6 7.0 6.6 6.6 6.6 15.8 102.0
Short Weierstrass, XYZZ 9.2 13.6 13.6 13.6 9.6 9.6 9.6 6.4 5.6 5.6 5.6 103.8
Short Weierstrass, XYZZ with a4=-3 8.6 13.6 13.6 13.6 9.6 9.6 9.6 6.4 5.6 5.6 5.6 103.8
Twisted Hessian, projective 7.8 12.0 12.0 12.0 12.0 12.0 12.0 7.8 12.0 12.0 12.0 12.0 12.8
Hessian, projective 7.8 12.0 10.8 15.6 10.0 10.0 10.0 5.4 8.0 7.0 8.0 12.0 12.8 102.0
Hessian, extended 7.8 10.8 10.8 10.8 9.8 9.8 9.8 7.8 9.8 9.8 9.8 104.6
Tripling-oriented Doche–Icart–Kohel, standard 7.6 15.8 14.8 15.8 10.2 10.2 10.2 5.0 5.6 5.6 5.6 10.8 103.8
Short Weierstrass, Jacobian 7.4 15.0 13.2 15.0 10.2 10.2 10.2 5.0 5.6 5.6 5.6 13.0 103.8
Twisted Edwards, extended 7.2 9.0 9.0 9.0 8.0 8.0 8.0 6.2 7.0 7.0 7.0 9.0 13.4
Twisted Edwards, extended with a=-1 7.2 8.0 8.0 8.0 7.0 7.0 7.0 6.2 6.0 6.0 6.0 8.0 13.4
Short Weierstrass, modified Jacobian 7.0 16.6 14.8 16.6 11.8 11.8 11.8 6.0 6.2 6.2 6.2
Short Weierstrass, Jacobian with a4=-3 7.0 15.0 13.2 15.0 10.2 10.2 10.2 5.0 5.6 5.6 5.6 12.6 103.8
Jacobi quartic, XYZ 6.8 12.4 10.4 12.8 10.4 10.4 10.4 4.2 6.6 6.6 6.6 12.4 102.8
Jacobi quartic, doubling-oriented XYZ 6.6 12.4 10.4 12.8 10.4 10.4 10.4 4.2 6.6 6.6 6.6 12.4 102.8
Twisted Edwards, projective 6.2 10.8 10.8 10.8 9.8 9.8 9.8 5.2 6.8 6.8 6.8 10.8 11.4
Edwards, projective 6.2 10.8 10.6 12.4 9.0 9.0 9.0 5.4 6.8 6.8 6.8 10.8 12.2 102.0
Edwards, inverted 6.2 9.8 9.8 9.8 8.8 8.8 8.8 5.4 7.0 7.0 7.0 9.8 12.2 102.0
Twisted Edwards, inverted 6.2 9.8 9.8 9.8 8.8 8.8 8.8 5.4 7.0 7.0 7.0 9.8
Doubling-oriented Doche–Icart–Kohel, standard 6.0 16.0 16.0 16.0 11.2 11.2 11.2 5.0 7.2 7.2 7.2 102.8
Short Weierstrass, Jacobian with a4=0 6.0 15.0 13.2 15.0 10.2 10.2 10.2 5.0 5.6 5.6 5.6 13.0 103.8
Jacobi intersection, projective 6.0 13.8 11.8 13.8 11.8 10.8 11.8 4.8 9.6 8.8 9.6 13.8 12.0 103.0
Jacobi intersection, extended 6.0 11.8 11.8 11.8 10.8 10.8 10.8 6.0 10.8 10.8 10.8 11.8 14.0 104.0
Jacobi quartic, XXYZZ 6.0 10.2 9.4 10.2 8.4 8.4 8.4 4.8 8.4 8.4 8.4 10.2 12.8 103.6
Jacobi quartic, doubling-oriented XXYZZ 6.0 10.2 9.4 10.2 8.4 8.4 8.4 4.8 8.4 8.4 8.4 10.2 12.8 103.6
Jacobi quartic, doubling-oriented XXYZZR 6.0 9.4 9.4 9.4 8.4 8.4 8.4 5.8 8.2 8.2 8.2 9.4 12.8 102.8
Jacobi quartic, XXYZZR 6.0 9.4 9.4 9.4 8.4 8.4 8.4 5.8 8.2 8.2 8.2 9.4 12.8 102.8
Short Weierstrass, XZ 6.0 6.0 8.6 7.6 14.6 13.6
Short Weierstrass, W12 with a6=0 5.8 15.6 14.8 15.6 12.0 12.0 12.0 5.8 12.0 12.0 12.0
Montgomery, XZ 3.6 2.6 5.6 4.6 9.2 8.2 101.0
Edwards, squared YZ with square d 3.2 2.4 5.6 4.6 8.8 7.8 101.0
Edwards, YZ with square d 3.2 1.6 7.2 6.2 8.8 7.8 101.0

Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:
Short Weierstrass, projective 9.02 13.34 13.34 13.34 10.34 10.34 10.34 6.35 6.34 6.34 6.34 15.02 102.00
Short Weierstrass, projective with a4=-1 9.02 13.34 13.34 13.34 10.34 10.34 10.34 6.35 6.34 6.34 6.34 15.01 102.00
Short Weierstrass, projective with a4=-3 9.01 13.34 13.34 13.34 10.34 10.34 10.34 6.35 6.34 6.34 6.34 15.02 102.00
Short Weierstrass, XYZZ 8.68 13.34 13.34 13.34 9.34 9.34 9.34 6.01 5.34 5.34 5.34 103.67
Short Weierstrass, XYZZ with a4=-3 8.34 13.34 13.34 13.34 9.34 9.34 9.34 6.01 5.34 5.34 5.34 103.67
Twisted Hessian, projective 7.67 12.00 12.00 12.00 12.00 12.00 12.00 7.67 12.00 12.00 12.00 12.00 12.02
Hessian, projective 7.02 12.00 10.02 14.04 10.00 10.00 10.00 5.01 8.00 7.00 8.00 12.00 12.02 102.00
Hessian, extended 7.02 10.02 10.02 10.02 9.02 9.02 9.02 7.02 9.02 9.02 9.02 104.34
Tripling-oriented Doche–Icart–Kohel, standard 6.69 15.02 14.02 15.02 9.68 9.68 9.68 4.35 5.34 5.34 5.34 10.02 103.67
Twisted Edwards, extended 6.68 9.00 9.00 9.00 8.00 8.00 8.00 5.68 7.00 7.00 7.00 9.00 13.01
Twisted Edwards, extended with a=-1 6.68 8.00 8.00 8.00 7.00 7.00 7.00 5.68 6.00 6.00 6.00 8.00 13.01
Short Weierstrass, Jacobian 6.36 14.35 12.68 14.35 9.68 9.68 9.68 4.35 5.34 5.34 5.34 11.70 103.67
Short Weierstrass, modified Jacobian 6.35 15.69 14.02 15.69 11.02 11.02 11.02 5.35 5.68 5.68 5.68
Short Weierstrass, Jacobian with a4=-3 6.35 14.35 12.68 14.35 9.68 9.68 9.68 4.35 5.34 5.34 5.34 11.69 103.67
Jacobi quartic, XYZ 6.02 12.01 10.01 12.02 10.01 10.01 10.01 3.68 6.34 6.34 6.34 12.01 102.67
Jacobi quartic, doubling-oriented XYZ 5.69 12.01 10.01 12.02 10.01 10.01 10.01 3.68 6.34 6.34 6.34 12.01 102.67
Twisted Edwards, projective 5.68 10.67 10.67 10.67 9.67 9.67 9.67 4.68 6.67 6.67 6.67 10.67 11.01
Edwards, projective 5.68 10.35 10.34 12.01 9.00 9.00 9.00 5.01 6.67 6.67 6.67 10.35 11.68 102.00
Edwards, inverted 5.68 9.67 9.67 9.67 8.67 8.67 8.67 5.01 7.00 7.00 7.00 9.67 11.68 102.00
Twisted Edwards, inverted 5.68 9.67 9.67 9.67 8.67 8.67 8.67 5.01 7.00 7.00 7.00 9.67
Doubling-oriented Doche–Icart–Kohel, standard 5.35 15.35 15.35 15.35 10.68 10.68 10.68 4.35 6.68 6.68 6.68 102.67
Short Weierstrass, Jacobian with a4=0 5.35 14.35 12.68 14.35 9.68 9.68 9.68 4.35 5.34 5.34 5.34 11.70 103.67
Jacobi intersection, projective 5.35 13.67 11.67 13.67 11.67 10.67 11.67 4.02 9.34 8.67 9.34 13.67 10.70 103.00
Jacobi intersection, extended 5.35 11.67 11.67 11.67 10.67 10.67 10.67 5.35 10.67 10.67 10.67 11.67 12.70 104.00
Jacobi quartic, XXYZZ 5.35 9.68 9.01 9.68 8.01 8.01 8.01 4.02 8.01 8.01 8.01 9.68 11.37 103.34
Jacobi quartic, doubling-oriented XXYZZ 5.35 9.68 9.01 9.68 8.01 8.01 8.01 4.02 8.01 8.01 8.01 9.68 11.37 103.34
Jacobi quartic, doubling-oriented XXYZZR 5.35 9.01 9.01 9.01 8.01 8.01 8.01 5.02 7.68 7.68 7.68 9.01 11.37 102.67
Jacobi quartic, XXYZZR 5.35 9.01 9.01 9.01 8.01 8.01 8.01 5.02 7.68 7.68 7.68 9.01 11.37 102.67
Short Weierstrass, XZ 5.35 5.35 8.34 7.34 13.69 12.69
Short Weierstrass, W12 with a6=0 5.02 14.69 14.02 14.69 11.35 11.35 11.35 5.02 11.35 11.35 11.35
Montgomery, XZ 3.34 2.34 5.34 4.34 8.68 7.68 101.00
Edwards, squared YZ with square d 2.68 2.01 5.34 4.34 8.02 7.02 101.00
Edwards, YZ with square d 2.68 1.34 6.68 5.68 8.02 7.02 101.00