Paper 2013/705

Symmetric Digit Sets for Elliptic Curve Scalar Multiplication without Precomputation

Clemens Heuberger and Michela Mazzoli


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 4-th and 6-th roots of unity act as (computationally efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-$w$-NAF (non-adjacent 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.

Available format(s)
Publication info
Preprint. MINOR revision.
elliptic curve cryptosystemimplementationnumber theoryscalar multiplicationFrobenius endomorphisminteger digit expansionsdigit sets$\tau$-adic expansionwidth-$w$ non-adjacent formGaussian integersEisenstein integers
Contact author(s)
clemens heuberger @ aau at
2013-11-03: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.