Paper 2007/455

Analysis and optimization of elliptic-curve single-scalar multiplication

Daniel J. Bernstein and Tanja Lange


Let $P$ be a point on an elliptic curve over a finite field of large characteristic. Exactly how many points $2P,3P,5P,7P,9P,\ldots,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 $\inversions/\mults$ 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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Elliptic curvesadditiondoublingexplicit formulasEdwards coordinatesinverted Edwards coordinatesside-channel countermeasuresunified addition formulasstrongly unified addition formulasprecomputations
Contact author(s)
tanja @ hyperelliptic org
2007-12-07: received
Short URL
Creative Commons Attribution


      author = {Daniel J.  Bernstein and Tanja Lange},
      title = {Analysis and optimization of elliptic-curve single-scalar multiplication},
      howpublished = {Cryptology ePrint Archive, Paper 2007/455},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.