Contemporary Mathematics Volume 461, 2008 Analysis and optimization of elliptic-curve single-scalar multiplication Daniel J. Bernstein and Tanja Lange Dedicated to Henri Cohen on the occasion of his sixtieth birthday. ABSTRACT. Let P be a point on an elliptic curve over a finite field of large characteristic. Exactly how many points 2P, 3P, 5P, 7 P, 9P, ... , mP should be precomputed in a sliding-window computation of nP? Should some or all of the points be converted to affine form, and at which moments during the precomputation should these conversions take place? Exactly how many field multiplications are required for the resulting computation of nP? The answers depend on the size of n, the 1/M ratio, the choice of curve shape, the choice of coordinate system, and the choice of addition formulas. This paper presents answers that, compared to previous analyses, are more carefully optimized and cover a much wider range of situations. 1. Introduction Consider the problem of computing a scalar multiple nP of a point P on an elliptic curve over a finite field of large characteristic. Cohen, Miyaji, and Ono, in a classic paper [12], analyzed the cost of a wide variety of scalar-multiplication methods and issued concrete recommendations for the lowest-cost methods. For example, for 160-bit scalars, Cohen, Miyaji, and Ono recommended one method using 41 + 1488.4M (i.e., 4 field inversions and on average 1488.4 field multiplica- tions a field squaring is implicitly counted as 0.8 field multiplications) and another method using 1610.2M. Both methods produce nP in Jacobian coordinates the second method is better if 1/M is large. In this paper we identify faster scalar-multiplication methods. For example, for 160-bit scalars, we obtain nP in Jacobian coordinates using just 11 + 1495.8M when 1/M is small, or 1573.8M when 1/M is large. Even better, for curves that allow the "a4 = -3" speedup, we obtain nP in Jacobian coordinates using just 2000 Mathematics Subject Classification. Primary 94A60. Secondary 12Y05, 14Q05. Permanent ID of this document: 8ac889630fe4d44913b92cc5914aa01b. Date: 2008.02.06. This work was supported in part by the National Science Foundation under grant ITR-Q716498 and in part by the European Commission through the 1ST Programme under Contract IST-2002- 507932 ECRYPT. Parts of this work were carried out while the first author was visiting Technische Universiteit Eindhoven. @2008 Daniel J. Bernstein and Tanja Lange 1 http://dx.doi.org/10.1090/conm/461/08979

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2008 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.