Table of costs of operations in elliptic curves

Elliptic curve cryptography is a popular form of public key encryption that is based on the mathematical theory of elliptic curves. Points on an elliptic curve can be added and form a group under this addition operation. This article describes the computational costs for this group addition and certain related operations that are used in elliptic curve cryptography algorithms.

Abbreviations for the operations

The next section presents a table of all the time-costs of some of the possible operations in elliptic curves. The columns of the table are labelled by various computational operations. The rows of the table are for different models of elliptic curves. These are the operations considered:

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.
DBL+ADD – Combined double-and-add step

To see how adding (ADD) and doubling (DBL) points on elliptic curves are defined, see The group law. The importance of doubling to speed scalar multiplication is discussed after the table. For information about other possible operations on elliptic curves see http://hyperelliptic.org/EFD/g1p/index.html.

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; one 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), or 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	DBL+ADD
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
Short Weierstrass Relative Jacobian	10	11	(7)	(7)		18
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

Importance of doubling

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. One way to do this is to compute successively:

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

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

$k=\sum _{i\leq \ell }k_{i}2^{i}$

with k_i ∈ {0,1} and ℓ = ⌊log₂ k⌋ and k_ℓ = 1, then:

${\begin{aligned}&[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\\&\qquad =[2^{l}]P+[k_{(l-1)}2^{l-1}]P+\dots +[k_{1}2]P+[k_{0}]P\end{aligned}}.$

This simple algorithm takes at most 2ℓ 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 then called square-and-multiply algorithm.

References

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