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: 57 Documents
Further Publications: http://www.hyperelliptic.org/EFD/bib.html
all top 5

Cited by 95 Authors

7 Costello, Craig
6 Hisil, Huseyin
6 Lange, Tanja
5 Wong, Kenneth Koon-Ho
4 Bernstein, Daniel Julius
4 Farashahi, Reza Rezaeian
3 Boyd, Colin A.
3 Carter, Gary
3 Dawson, Edward
3 Diao, Oumar
3 Fouotsa, Emmanuel
3 González Nieto, Juan Manuel
3 Joye, Marc
3 Lauter, Kristin Estella
3 Moody, Dustin
3 Naehrig, Michael
3 Wu, Hongfeng
2 Bos, Joppe W.
2 Doche, Christophe
2 Galbraith, Steven D.
2 Grebnev, S. V.
2 Lin, Xibin
2 Nitaj, Abderrahmane
2 Sica, Francesco
1 Agievich, Sergeĭ Valer’evich
1 Arène, Christophe
1 Batina, Lejla
1 Bauer, Aurélie
1 Belkasmi, Mostafa
1 Birkner, Peter
1 Boudabra, Maher
1 Brumley, Billy Bob
1 Budhathoki, Parshuram
1 Castryck, Wouter
1 Çelik, Türkü Özlüm
1 Chen, Tien-Ren
1 Cheng, Chen-Mou
1 Chi-Domínguez, Jesús-Javier
1 Devigne, Julien
1 Dygin, D. M.
1 Fan, Junfeng
1 Fan, Xinxin
1 Feng, Rongquan
1 Gallin, Gabriel
1 Gebotys, Catherine H.
1 Gu, Dawu
1 Gu, Haihua
1 Heer, Henriette
1 Herbaut, Fabien
1 Hosseini, Seyed Gholamhossein
1 Hutter, Michael
1 Ionica, Sorina
1 Jancar, Jan
1 Jaulmes, Éliane
1 Joux, Antoine
1 Karati, Sabyasachi
1 Kohel, David R.
1 Liardet, Pierre-Yvan
1 Lin, Dongdai
1 Longa, Patrick
1 McGuire, Gary
1 Meloni, Nicolas
1 Montgomery, Peter Lawrence
1 Nie, Menglong
1 Otemissov, Adilet
1 Pedersen, Robi
1 Peters, Christiane
1 Poruchnik, S. V.
1 Prouff, Emmanuel
1 Reinhard, Jean-René
1 Ritzenthaler, Christophe
1 Robert, Jean-Marc
1 Robinson, Oisín
1 Sarkar, Palash
1 Sedláček, Vladimír
1 Semenov, Vladimir I.
1 Semmouni, Meryem Cherkaoui
1 Shparlinski, Igor E.
1 Sidorenko, Andrey
1 Sierra, Yannick
1 Steinwandt, Rainer
1 Sutantyo, Daniel
1 Taleb, Abdul Rahman
1 Teglia, Yannick
1 Tisserand, Arnaud
1 Uzunkol, Osmanbey
1 Vasilenko, O. N.
1 Verbauwhede, Ingrid M. R.
1 Vercauteren, Frederik
1 Vergnaud, Damien
1 Véron, Pascal
1 Wild, Justine
1 Xie, WenLu
1 Yang, Bo-Yin
1 Zhang, Xusheng

Citations by Year