
Proceedings Paper
Optimizing elliptic curve scalar multiplication for small scalarsFormat | Member Price | Non-Member Price |
---|---|---|
$17.00 | $21.00 |
Paper 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 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).
Paper Details
Date Published: 3 September 2009
PDF: 10 pages
Proc. SPIE 7444, Mathematics for Signal and Information Processing, 74440N (3 September 2009); doi: 10.1117/12.827689
Published in SPIE Proceedings Vol. 7444:
Mathematics for Signal and Information Processing
Franklin T. Luk; Mark S. Schmalz; Gerhard X. Ritter; Junior Barrera; Jaakko T. Astola, Editor(s)
PDF: 10 pages
Proc. SPIE 7444, Mathematics for Signal and Information Processing, 74440N (3 September 2009); doi: 10.1117/12.827689
Show Author Affiliations
Pascal Giorgi, LIRMM, CNRS, Univ. Montpellier 2 (France)
Laurent Imbert, LIRMM, CNRS, Univ. Montpellier 2 (France)
PIMS, CNRS, Univ. of Calgary (Canada)
Laurent Imbert, LIRMM, CNRS, Univ. Montpellier 2 (France)
PIMS, CNRS, Univ. of Calgary (Canada)
Thomas Izard, LIRMM, CNRS, Univ. Montpellier 2 (France)
Published in SPIE Proceedings Vol. 7444:
Mathematics for Signal and Information Processing
Franklin T. Luk; Mark S. Schmalz; Gerhard X. Ritter; Junior Barrera; Jaakko T. Astola, Editor(s)
© SPIE. Terms of Use
