Optimizing elliptic curve scalar multiplication for small scalars

Pascal Giorgi; Laurent Imbert; Thomas Izard

doi:10.1117/12.827689

3 September 2009 Optimizing elliptic curve scalar multiplication for small scalars

Pascal Giorgi, Laurent Imbert, Thomas Izard

Proceedings Volume 7444, Mathematics for Signal and Information Processing; 74440N (2009) https://doi.org/10.1117/12.827689
Event: SPIE Optical Engineering + Applications, 2009, San Diego, California, United States

Abstract

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 F_q. 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).

Citation Download Citation

Pascal Giorgi, Laurent Imbert, and Thomas Izard "Optimizing elliptic curve scalar multiplication for small scalars", Proc. SPIE 7444, Mathematics for Signal and Information Processing, 74440N (3 September 2009); https://doi.org/10.1117/12.827689

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available