Analysis and optimization of elliptic-curve single-scalar multiplication

D.J. Bernstein, T. Lange

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 11M 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.
Original languageEnglish
Title of host publicationFinite Fields and Applications (Proceedings 8th International Conference, Fq8, Melbourne, Australia, July 9-13, 2007)
EditorsG.L. Mullen, D. Panario, I.E. Shparlinski
Place of PublicationProvidence RI
PublisherAmerican Mathematical Society
Pages1-20
ISBN (Print)978-0-8218-4309-3
Publication statusPublished - 2008

Publication series

NameContemporary Mathematics Series
Volume461
ISSN (Print)0271-4132

Fingerprint Dive into the research topics of 'Analysis and optimization of elliptic-curve single-scalar multiplication'. Together they form a unique fingerprint.

Cite this