Cryptology ePrint Archive: Report 2007/455
Analysis and optimization of elliptic-curve single-scalar multiplication
Daniel J. Bernstein and Tanja Lange
Abstract: 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.
Category / Keywords: public-key cryptography / Elliptic curves, addition, doubling, explicit formulas, Edwards coordinates, inverted Edwards coordinates, side-channel countermeasures, unified addition formulas, strongly unified addition formulas. precomputations
Date: received 7 Dec 2007
Contact author: tanja at hyperelliptic org
Available format(s): PDF | BibTeX Citation
Version: 20071207:150254 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]