Explicit-Formulas Database

# Ordinary genus-1 curves over binary fields

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

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^3+y^3+1=3*d*x*y

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

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

Affine coordinates: x=X, y=Y
Extended Lopez-Dahab coordinates with a2=0: x=X/Z, y=Y/ZZ, ZZ=Z2, XZ=X*Z, a2=0
Extended Lopez-Dahab coordinates with a2=1: x=X/Z, y=Y/Z2, ZZ=Z2, a2=1
Jacobian coordinates: x=X/Z2, y=Y/Z3
Lambda coordinates: x=X/Z, y/x=(L-X)/Z
Lopez-Dahab coordinates with a2=0: x=X/Z, y=Y/Z2, a2=0
Lopez-Dahab coordinates with a2=1: x=X/Z, y=Y/Z2, a2=1
Lopez-Dahab coordinates: x=X/Z, y=Y/Z2
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.
• 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=10M, S=0M, *param=0M, add=0M, *const=0M:
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:
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