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 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 $$, where $$ is a zero of the characteristic polynomial $$ 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 $$ 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.