Fandom

DSZQUP XJLJ

Table of costs of operations in elliptic curves

566pages on
this wiki
Add New Page
Talk0 Share

Template:Technical

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.

For more information about other possible operations on elliptic curves see http://hyperelliptic.org/EFD/g1p/index.html.

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
ADD - Addition
mADD - Mixed addition: addition of an input that has been scaled to have Z-coordinate 1.
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.

For more information about other results obtained with different assumptions, see http://hyperelliptic.org/EFD/g1p/index.html

Curve shape, representation DBL ADD mADD mDBL TPL
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

ReferencesEdit

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.