## EFD

swMATH ID: | 4152 |

Software Authors: | Daniel J. Bernstein; Tanja Lange |

Description: | Explicit-Formulas Database: Analysis and optimization of elliptic-curve single-scalar multiplication. The authors study the elliptic-curve single-scalar multiplication over finite fields, i.e. given a finite field k (the ground field), an elliptic curve E (with small parameters), an integer n (the scalar) and a point P∈E(k), they identify today’s fastest methods to compute the point nP on E. Due to the well-known cryptographic applications, tables and figures are given for 160, 256 and 512-bit scalars, expressing the necessary number of multiplications per bit as a function of the I/M ratio, i.e. the number of multiplications needed to provide an inversion in the ground field. In order to do this, the authors first consider the problem of adding two points (or doubling a point). They look at twelve different coordinate systems: Projective, Jacobian (these two systems are also considered in the particular, faster, case a 4 =-3), Doubling (resp. Tripling)-oriented Doche/Icart/Kohel, Montgomery, Jacobi intersections, Jacobi quartics, Hessian, Edwards and inverted Edwards. For each system, the relation with the classical Weierstrass model and the corresponding (affine) coordinates is given. Note that certain systems do not provide a model for every elliptic curve. Since the precomputation of some little multiples 2P,3P,5P,7P,⋯,mP is necessary, they look for the optimal odd m (always less than 31), constructing for each m,n an “addition-subtraction” chain, that allows a fast computation of nP. In order to do this, they combine “windows” techniques, and average over many random scalars of given size to get the best choice. Finally, the authors consider four cases, allowing zero, one, two or three inversions in the ground field (typically, an inversion is needed when one wants to give the affine coordinates of a point). Then they compare their respective performances when the ratio I/M varies. All the results are summarized in three tables, and the fastest ones in three figures, giving a clear account of what is known about this problem nowadays. Note also that all these results are updated at the address http://hyperelliptic.org/EFD. |

Homepage: | http://www.hyperelliptic.org/EFD/ |

Keywords: | Explicit-Formulas Database |

Related Software: | Curve25519; mpFq; SageMath; eBACS; eBASH; gmp; HECC; Magma; OpenSSL; eBATS; MIRACL; KummerLineV02; Connecting Legendre; GitHub; AVIsogenies; ISOLATE; EECM-MPFQ; JKL-ECM; GMP-ECM; Echidna |

Cited in: | 54 Publications |

Further Publications: | http://www.hyperelliptic.org/EFD/bib.html |

all
top 5

### Cited by 86 Authors

all
top 5

### Cited in 19 Serials

all
top 5