Ordinary genus-1 curves over binary fields

Binary Edwards curves: d1(x+y)+d2(x^²+y^²)=(x+x^²)*(y+y^²)

W coordinates with d1=d2: x+y=w, d1=d2
W coordinates: x+y=w
WZ coordinates with d1=d2: x+y=W/Z, d1=d2
WZ coordinates: x+y=W/Z
Affine coordinates with d1=d2: x=X, y=Y, d1=d2
Affine coordinates: x=X, y=Y
Projective coordinates with d1=d2: x=X/Z, y=Y/Z, d1=d2
Projective coordinates: x=X/Z, y=Y/Z

Hessian curves: x^³+y^³+1=3dx*y

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

Short Weierstrass curves: y^²+xy=x^³+a2x^²+a6

Affine coordinates: x=X, y=Y
Extended Lopez-Dahab coordinates with a2=0: x=X/Z, y=Y/ZZ, ZZ=Z^², XZ=X*Z, a2=0
Extended Lopez-Dahab coordinates with a2=1: x=X/Z, y=Y/Z^², ZZ=Z^², a2=1
Jacobian coordinates: x=X/Z^², y=Y/Z^³
Lambda coordinates: x=X/Z, y/x=(L-X)/Z
Lopez-Dahab coordinates with a2=0: x=X/Z, y=Y/Z^², a2=0
Lopez-Dahab coordinates with a2=1: x=X/Z, y=Y/Z^², a2=1
Lopez-Dahab coordinates: x=X/Z, y=Y/Z^²
Projective coordinates: x=X/Z, y=Y/Z
XZ coordinates: x=X/Z

The EFD currently includes 135 explicit formulas for addition, doubling, tripling, and scaling of points in 19 representations on 3 shapes of ordinary genus-1 curves over binary fields.

Speed tables

The following speed tables distinguish between eighteen different operations:

DBL: Doubling. P1 |-> P1+P1.
ADD: Addition. P1,P2 |-> P1+P2.
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 Z1^², Z1^³, Z2^², and Z2^³; caching Z2^² and Z2^³ saves 1M+1S in a readdition of (X2:Y2:Z2).
preADD: Preaddition; i.e., addition compatible with the fastest readdition. Sometimes ADD is faster than preADD because there are faster addition formulas providing slower readdition.
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.
mreADD: Mixed readdition.
mpreADD: Mixed preaddition.
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.
mmpreADD.
SUNI: Strongly unified addition; i.e., addition that also works without change for doubling.
TPL: Tripling. P1 |-> P1+P1+P1.
DADD: Differential addition, i.e., addition of points whose difference is known. P3-P2,P2,P3 |-> P3+P2.
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=10M, S=0M, *param=0M, add=0M, *const=0M:

Curve shape, representation DBL ADD reADD preADD mADD mreADD mpreADD mDBL mmADD mmreADD mmpreADD SUNI TPL DADD mDADD LADD mLADD SCALE

Binary Edwards, affine 12 28 27 28 28 27 28 12 28 27 28 28 0

Short Weierstrass, affine 12 12 12 12 12 12 12 12 12 12 12 0

Binary Edwards, affine with d1=d2 11 28 27 28 28 27 28 11 28 27 28 28 0

Binary Edwards, w 11 11 13 13 24 24 0

Binary Edwards, w with d1=d2 10 10 11 11 21 21 0

Short Weierstrass, projective 7 14 14 14 11 11 11 5 7 7 7 12

Hessian, projective 6 12 9 12 10 9 12 6 8 7 8 11 12

Short Weierstrass, Jacobian 4 14 13 14 10 10 10 1 10 10 10 13

Short Weierstrass, Lopez-Dahab with a2=1 3 13 13 13 8 8 8 1 5 5 5

Short Weierstrass, Lopez-Dahab with a2=0 3 13 13 13 8 8 8 1 5 5 5

Short Weierstrass, Lopez-Dahab 3 13 13 13 8 8 8 1 5 5 5

Short Weierstrass, Lambda 3 11 11 11 11 11 11 3 11 11 11

Binary Edwards, projective 2 18 18 18 13 13 13 2 13 13 13 18 12

Binary Edwards, projective with d1=d2 2 16 16 16 13 13 13 2 13 13 13 16 12

Short Weierstrass, extended Lopez-Dahab with a2=0 2 14 14 14 9 9 9 2 9 9 9

Short Weierstrass, extended Lopez-Dahab with a2=1 2 13 13 13 8 8 8 2 8 8 8

Binary Edwards, WZ 1 1 6 6 8 6 11

Binary Edwards, WZ with d1=d2 1 1 6 5 7 5 11

Short Weierstrass, XZ 1 0 5 4 6 5 11

Curve shape, representation	DBL	ADD	reADD	preADD	mADD	mreADD	mpreADD	mDBL	mmADD	mmreADD	mmpreADD	SUNI	TPL	DADD	mDADD	LADD	mLADD	SCALE
Binary Edwards, affine	12	28	27	28	28	27	28	12	28	27	28	28						0
Short Weierstrass, affine	12	12	12	12	12	12	12	12	12	12	12							0
Binary Edwards, affine with d1=d2	11	28	27	28	28	27	28	11	28	27	28	28						0
Binary Edwards, w	11							11						13	13	24	24	0
Binary Edwards, w with d1=d2	10							10						11	11	21	21	0
Short Weierstrass, projective	7	14	14	14	11	11	11	5	7	7	7							12
Hessian, projective	6	12	9	12	10	9	12	6	8	7	8		11					12
Short Weierstrass, Jacobian	4	14	13	14	10	10	10	1	10	10	10							13
Short Weierstrass, Lopez-Dahab with a2=1	3	13	13	13	8	8	8	1	5	5	5
Short Weierstrass, Lopez-Dahab with a2=0	3	13	13	13	8	8	8	1	5	5	5
Short Weierstrass, Lopez-Dahab	3	13	13	13	8	8	8	1	5	5	5
Short Weierstrass, Lambda	3	11	11	11	11	11	11	3	11	11	11
Binary Edwards, projective	2	18	18	18	13	13	13	2	13	13	13	18						12
Binary Edwards, projective with d1=d2	2	16	16	16	13	13	13	2	13	13	13	16						12
Short Weierstrass, extended Lopez-Dahab with a2=0	2	14	14	14	9	9	9	2	9	9	9
Short Weierstrass, extended Lopez-Dahab with a2=1	2	13	13	13	8	8	8	2	8	8	8
Binary Edwards, WZ	1							1						6	6	8	6	11
Binary Edwards, WZ with d1=d2	1							1						6	5	7	5	11
Short Weierstrass, XZ	1							0						5	4	6	5	11

Smallest multiplication counts assuming I=10M, S=0.2M, *param=0M, add=0M, *const=0M:

Curve shape, representation DBL ADD reADD preADD mADD mreADD mpreADD mDBL mmADD mmreADD mmpreADD SUNI TPL DADD mDADD LADD mLADD SCALE

Binary Edwards, affine 12.8 28.4 27.4 28.4 28.4 27.4 28.4 12.8 28.4 27.4 28.4 28.4 0.0

Short Weierstrass, affine 12.2 12.2 12.2 12.2 12.2 12.2 12.2 12.2 12.2 12.2 12.2 0.0

Binary Edwards, affine with d1=d2 11.8 28.4 27.4 28.4 28.4 27.4 28.4 11.8 28.4 27.4 28.4 28.4 0.0

Binary Edwards, w 11.4 11.4 13.2 13.2 24.6 24.6 0.0

Binary Edwards, w with d1=d2 10.4 10.4 11.4 11.4 21.6 21.6 0.0

Short Weierstrass, projective 7.6 14.2 14.2 14.2 11.2 11.2 11.2 5.6 7.2 7.2 7.2 12.0

Hessian, projective 6.6 12.0 9.6 13.2 10.0 9.6 13.2 6.6 8.0 7.0 8.0 11.8 12.0

Short Weierstrass, Jacobian 5.0 15.0 13.8 15.0 10.6 10.6 10.6 1.4 10.6 10.6 10.6 13.2

Short Weierstrass, Lopez-Dahab with a2=1 4.0 13.8 13.6 13.8 9.0 9.0 9.0 1.6 5.6 5.6 5.6

Short Weierstrass, Lopez-Dahab with a2=0 4.0 13.8 13.6 13.8 9.0 9.0 9.0 1.6 5.6 5.6 5.6

Short Weierstrass, Lopez-Dahab 4.0 13.8 13.6 13.8 9.0 9.0 9.0 1.6 5.6 5.6 5.6

Short Weierstrass, Lambda 3.8 11.4 11.4 11.4 11.4 11.4 11.4 3.8 11.4 11.4 11.4

Binary Edwards, projective 3.2 18.4 18.4 18.4 13.6 13.2 13.6 3.2 13.6 13.2 13.6 18.4 12.0

Binary Edwards, projective with d1=d2 3.0 16.2 16.2 16.2 13.6 13.2 13.6 3.0 13.6 13.2 13.6 16.2 12.0

Short Weierstrass, extended Lopez-Dahab with a2=0 3.0 14.6 14.6 14.6 9.8 9.8 9.8 2.6 9.8 9.8 9.8

Short Weierstrass, extended Lopez-Dahab with a2=1 2.8 13.6 13.6 13.6 8.8 8.8 8.8 2.8 8.8 8.8 8.8

Binary Edwards, WZ 1.6 1.6 6.4 6.2 8.8 6.8 11.0

Binary Edwards, WZ with d1=d2 1.6 1.6 6.4 5.2 7.8 5.8 11.0

Short Weierstrass, XZ 1.6 0.4 5.6 4.2 7.0 5.8 11.0

Curve shape, representation	DBL	ADD	reADD	preADD	mADD	mreADD	mpreADD	mDBL	mmADD	mmreADD	mmpreADD	SUNI	TPL	DADD	mDADD	LADD	mLADD	SCALE
Binary Edwards, affine	12.8	28.4	27.4	28.4	28.4	27.4	28.4	12.8	28.4	27.4	28.4	28.4						0.0
Short Weierstrass, affine	12.2	12.2	12.2	12.2	12.2	12.2	12.2	12.2	12.2	12.2	12.2							0.0
Binary Edwards, affine with d1=d2	11.8	28.4	27.4	28.4	28.4	27.4	28.4	11.8	28.4	27.4	28.4	28.4						0.0
Binary Edwards, w	11.4							11.4						13.2	13.2	24.6	24.6	0.0
Binary Edwards, w with d1=d2	10.4							10.4						11.4	11.4	21.6	21.6	0.0
Short Weierstrass, projective	7.6	14.2	14.2	14.2	11.2	11.2	11.2	5.6	7.2	7.2	7.2							12.0
Hessian, projective	6.6	12.0	9.6	13.2	10.0	9.6	13.2	6.6	8.0	7.0	8.0		11.8					12.0
Short Weierstrass, Jacobian	5.0	15.0	13.8	15.0	10.6	10.6	10.6	1.4	10.6	10.6	10.6							13.2
Short Weierstrass, Lopez-Dahab with a2=1	4.0	13.8	13.6	13.8	9.0	9.0	9.0	1.6	5.6	5.6	5.6
Short Weierstrass, Lopez-Dahab with a2=0	4.0	13.8	13.6	13.8	9.0	9.0	9.0	1.6	5.6	5.6	5.6
Short Weierstrass, Lopez-Dahab	4.0	13.8	13.6	13.8	9.0	9.0	9.0	1.6	5.6	5.6	5.6
Short Weierstrass, Lambda	3.8	11.4	11.4	11.4	11.4	11.4	11.4	3.8	11.4	11.4	11.4
Binary Edwards, projective	3.2	18.4	18.4	18.4	13.6	13.2	13.6	3.2	13.6	13.2	13.6	18.4						12.0
Binary Edwards, projective with d1=d2	3.0	16.2	16.2	16.2	13.6	13.2	13.6	3.0	13.6	13.2	13.6	16.2						12.0
Short Weierstrass, extended Lopez-Dahab with a2=0	3.0	14.6	14.6	14.6	9.8	9.8	9.8	2.6	9.8	9.8	9.8
Short Weierstrass, extended Lopez-Dahab with a2=1	2.8	13.6	13.6	13.6	8.8	8.8	8.8	2.8	8.8	8.8	8.8
Binary Edwards, WZ	1.6							1.6						6.4	6.2	8.8	6.8	11.0
Binary Edwards, WZ with d1=d2	1.6							1.6						6.4	5.2	7.8	5.8	11.0
Short Weierstrass, XZ	1.6							0.4						5.6	4.2	7.0	5.8	11.0

Ordinary genus-1 curves over binary fields

Binary Edwards curves: d1*(x+y)+d2*(x^2+y^2)=(x+x^2)*(y+y^2)

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

Short Weierstrass curves: y^2+x*y=x^3+a2*x^2+a6

Speed tables

Binary Edwards curves: d1(x+y)+d2(x^²+y^²)=(x+x^²)*(y+y^²)

Hessian curves: x^³+y^³+1=3dx*y

Short Weierstrass curves: y^²+xy=x^³+a2x^²+a6