Explicit-Formulas Database
Ordinary genus-1 curves over binary fields
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
Affine coordinates: x=X, y=Y
Extended Lopez-Dahab coordinates with a2=0: x=X/Z, y=Y/ZZ, ZZ=Z^2, XZ=X*Z, a2=0
Extended Lopez-Dahab coordinates with a2=1: x=X/Z, y=Y/Z^2, ZZ=Z^2, a2=1
Jacobian coordinates: x=X/Z^2, y=Y/Z^3
Lopez-Dahab coordinates with a2=0: x=X/Z, y=Y/Z^2, a2=0
Lopez-Dahab coordinates with a2=1: x=X/Z, y=Y/Z^2, a2=1
Lopez-Dahab coordinates: x=X/Z, y=Y/Z^2
Projective coordinates: x=X/Z, y=Y/Z
The EFD currently includes
102
explicit formulas for addition, doubling, tripling, and scaling of points in
16
representations on
2
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^2, Z1^3, Z2^2, and Z2^3;
caching Z2^2 and Z2^3 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 reADD
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 |
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 |
| 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 |
|
|
|
|
|
|
| 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 |
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 |
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 |
| 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 |
|
|
|
|
|
|
| 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 |