Paper 2013/705
Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation
Clemens Heuberger and Michela Mazzoli
Abstract
We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely $E: y^2 = x^3 + Ax$ in prime characteristic $p\equiv 1$ mod~4, and $E: y^2 = x^3 + B$ in prime characteristic $p\equiv 1$ mod 3. On these curves, the 4th and 6th roots of unity act as (computationally efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width$w$NAF (nonadjacent form) digit expansion of positive integers to the complex base of $\tau$, where $\tau$ is a zero of the characteristic polynomial $x^2  tx + p$ of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo $\tau$ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Keywords
 elliptic curve cryptosystemimplementationnumber theoryscalar multiplicationFrobenius endomorphisminteger digit expansionsdigit sets$\tau$adic expansionwidth$w$ nonadjacent formGaussian integersEisenstein integers
 Contact author(s)
 clemens heuberger @ aau at
 History
 20131103: received
 Short URL
 https://ia.cr/2013/705
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/705, author = {Clemens Heuberger and Michela Mazzoli}, title = {Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation}, howpublished = {Cryptology ePrint Archive, Paper 2013/705}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/705}}, url = {https://eprint.iacr.org/2013/705} }