Table of costs of operations in elliptic curves

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

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:

${\displaystyle 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

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

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

${\displaystyle {\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.

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