Set function

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 operations

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,[2]P=P+P,[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}_i{2}^i$

with k_i in {0,1} and $l=[lo{g}_{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_{1}2]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 ≠ 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: <poem> 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. </poem>

Tabulation

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

References

• http://hyperelliptic.org/EFD/g1p/index.html