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 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 Arène, Christophe 1 Batina, Lejla 1 Bauer, Aurélie 1 Belkasmi, Mostafa 1 Birkner, Peter 1 Boudabra, Maher 1 Budhathoki, Parshuram 1 Castryck, Wouter 1 Çelik, Türkü Özlüm 1 Chen, Tien-Ren 1 Cheng, Chen-Mou 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 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 Peters, Christiane 1 Prouff, Emmanuel 1 Reinhard, Jean-René 1 Ritzenthaler, Christophe 1 Robert, Jean-Marc 1 Robinson, Oisín 1 Sarkar, Palash 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 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 all top 5 Cited in 19 Serials 3 Journal of Cryptology 3 Matematicheskie Voprosy Kriptografii 2 Journal of Number Theory 2 Designs, Codes and Cryptography 2 Afrika Matematika 1 Information Processing Letters 1 Mathematics of Computation 1 Journal of Computer and System Sciences 1 Theoretical Computer Science 1 Journal of Symbolic Computation 1 Finite Fields and their Applications 1 Journal of Discrete Mathematical Sciences & Cryptography 1 LMS Journal of Computation and Mathematics 1 Journal of Applied Mathematics and Computing 1 Quantum Information Processing 1 Mediterranean Journal of Mathematics 1 Journal of Mathematical Cryptology 1 Advances in Mathematics of Communications 1 Cryptography and Communications all top 5 Cited in 8 Fields 42 Information and communication theory, circuits (94-XX) 34 Algebraic geometry (14-XX) 27 Number theory (11-XX) 5 Computer science (68-XX) 1 Field theory and polynomials (12-XX) 1 Numerical analysis (65-XX) 1 Quantum theory (81-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX) Citations by Year