**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 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.

**Category / Keywords: **implementation / elliptic curve cryptosystem, implementation, number theory, scalar multiplication, Frobenius endomorphism, integer digit expansions, digit sets, $\tau$-adic expansion, width-$w$ non-adjacent form, Gaussian integers, Eisenstein integers

**Date: **received 29 Oct 2013

**Contact author: **clemens heuberger at aau at

**Available format(s): **PDF | BibTeX Citation

**Version: **20131103:170607 (All versions of this report)

**Short URL: **ia.cr/2013/705

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]