3 September 2009 Optimizing elliptic curve scalar multiplication for small scalars
Author Affiliations +
On an elliptic curve, the multiplication of a point P by a scalar k is defined by a series of operations over the field of definition of the curve E, usually a finite field Fq. The computational cost of [k]P = P + P + ...+ P (k times) is therefore expressed as the number of field operations (additions, multiplications, inversions). Scalar multiplication is usually computed using variants of the binary algorithm (double-and-add, NAF, wNAF, etc). If s is a small integer, optimized formula for [s]P can be used within a s-ary algorithm or with double-base methods with bases 2 and s. Optimized formulas exists for very small scalars (s ≤ 5). However, the exponential growth of the number of field operations makes it a very difficult task when s > 5. We present a generic method to automate transformations of formulas for elliptic curves over prime fields in various systems of coordinates. Our method uses a directed acyclic graph structure to find possible common subexpressions appearing in the formula and several arithmetic transformations. It produces efficient formulas to compute [s]P for a large set of small scalars s. In particular, we present a faster formula for [5]P in Jacobian coordinates. Moreover, our program can produce code for various mathematical software (Magma) and libraries (PACE).
© (2009) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Pascal Giorgi, Pascal Giorgi, Laurent Imbert, Laurent Imbert, Thomas Izard, Thomas Izard, } "Optimizing elliptic curve scalar multiplication for small scalars", Proc. SPIE 7444, Mathematics for Signal and Information Processing, 74440N (3 September 2009); doi: 10.1117/12.827689; https://doi.org/10.1117/12.827689


High-speed floating-point divider with reduced area
Proceedings of SPIE (September 03 2009)
On converting numbers to the double-base number system
Proceedings of SPIE (October 25 2004)
Pseudo-random generator based on Chinese Remainder Theorem
Proceedings of SPIE (September 03 2009)
Image Processing By A Local-SIND Co-Processor
Proceedings of SPIE (April 20 1986)

Back to Top