IACR News item: 03 November 2013
Clemens Heuberger, Michela Mazzoli
ePrint Reportordinary 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.
Additional news items may be found on the IACR news page.