Symmetric digit sets for elliptic curve scalar multiplication without precomputation
Clemens Heuberger, Michela Mazzoli · Theoretical Computer Science · 2014
We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely E : y 2 = x 3 + A x in prime characteristic p ≡ 1 mod 4 , and E : y 2 = x 3 + B in prime characteristic p ≡ 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 x 2 − t x + 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 τ 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.