title: Symmetric digit sets for elliptic curve scalar multiplication without precomputation.
abstract: We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely [Formula: see text] in prime characteristic [Formula: see text], and [Formula: see text] in prime characteristic [Formula: see text]. 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 [Formula: see text] 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.
authors.affiliation: Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstrasse 65-67, 9020 Klagenfurt am Wörthersee, Austria.
authors.forename: Clemens
authors.initials: C
authors.lastname: Heuberger
authors.affiliation: Institut für Mathematik, Alpen-Adria-Universität Klagenfurt, Universitätsstrasse 65-67, 9020 Klagenfurt am Wörthersee, Austria.
authors.forename: Michela
authors.initials: M
authors.lastname: Mazzoli
keywords: Eisenstein integers; Elliptic curve scalar multiplication; Frobenius endomorphism; Gaussian integers; Integer digit expansion; Width-w Non-Adjacent Form