FANDOM

567 Pages

nkbhguhgjbhkjnlmnjkghiguf7rftybkjbhufrsr4etfugyug97r45w3wr76tgyuhijjknkl{{Infobox{{Delete{{Navbox}}}}}}

This table relates to the computational cost for certain operations used in elliptic curve cryptography, used in practice for strong cryptographic security of a public key system. The columns of the table are labelled by various computational steps. The rows of the table are for different models of elliptic curves. The table below contains the time-cost for these operations:

Abbreviations for the operationsEdit

In the next section a table of all the costs of some of the possible operations in elliptic curves is given. In some applications of elliptic curve cryptography and the elliptic curve method of factorization (ECM) it is necessary to consider the scalar multiplication $[n]P$. So, one way to do this is to compute successively:

$P,\quad [2]P=P+P,\quad [3]P=[2]P+P, \dots , [n]P=[n-1]P+P$

But, it is faster to use double-and-add method, $e.g. [5]P=[2]([2]P)+P$. In general to compute $[k]P$,write

$k=\sum_{i\le l}k_i2^i$

with $k_i$ in {0,1} and $l=[log_2 k]$, $k_l=1$, then:

$[2](....([2]([2]([2]([2]([2]P+[k_{(l-1)}]P)+[k_{(l-2)}]P)+[k_{(l-3)}]P)+ \dots ) \dots +[k_1]P)+[k_0]P= [2^l]P+[k_{(l-1)}2^{l-1}]P+ \dots +[k_12]P+[k_0]P$.

Note that, this simple algorithm takes at most 2l steps and each step consists of a doubling and (if $k_i\ne 0$) adding two points. So, this is one of the reasons why addition and doubling formulas are defined. Furthermore, this method is applicable to any group and if the group law is written multiplicatively, the double-and-add algorithm is instead called square-and-multiply algorithm.

To see what adding (ADD) and doubling (DBL) points on elliptic curves mean, see The group law.

These are the operations considered in the table below:

DBL - Doubling
mDBL - Mixed doubling: doubling of an input that has been scaled to have Z coordinate 1.
TPL - Tripling.

TabulationEdit

Under different assumptions on the multiplication, addition, inversion for the elements in some fixed field, the time-cost of these operations varies. In this table it is assumed that:

I = 100M, S = 1M, *param = 0M, add = 0M, *const = 0M

This means that 100 multiplications (M) are required to invert (I) an element; 1 multiplication is required to compute the square (S) of an element; no multiplication is needed to multiply an element by a parameter (*param), by a constant (*const), nor to add two elements.

Short Weierstrass projective 11 14 11 8
Short Weierstrass projective with a4=-1 11 14 11 8
Short Weierstrass projective with a4=-3 10 14 11 8
Tripling-oriented Doche–Icart–Kohel curve 9 17 11 6 12
Hessian curve extended 9 12 11 9
Hessian curve projective 8 12 10 6 14
Jacobi quartic XYZ 8 13 11 5
Jacobi quartic doubling-oriented XYZ 8 13 11 5
Twisted Hessian curve projective 8 12 12 8 14
Doubling-oriented Doche–Icart–Kohel curve 7 17 12 6
Jacobi intersection projective 7 14 12 6 14
Jacobi intersection extended 7 12 11 7 16
Twisted Edwards projective 7 11 10 6
Twisted Edwards Inverted 7 10 9 6
Twisted Edwards Extended 8 9 8 7
Edwards projective 7 11 9 6 13
Jacobi quartic doubling-oriented XXYZZ 7 11 9 6 14
Jacobi quartic XXYZZ 7 11 9 6 14
Jacobi quartic XXYZZR 7 10 9 7 15
Edwards curve inverted 7 10 9 6
Montgomery curve 4 3