Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases

Heuberger, Clemens¹ ; Krenn, Daniel²

¹ Institute of Mathematics Alpen-Adria-Universität Klagenfurt Universitätsstraße 65–67, 9020 Klagenfurt am Wörthersee, Austria
² Institute of Optimisation and Discrete Mathematics (Math B) Graz University of Technology Steyrergasse 30/II, 8010 Graz, Austria

Journal de théorie des nombres de Bordeaux, Tome 25 (2013) no. 2, pp. 353-386

Abstract (VO)

We consider digit expansions ${\sum }_{j=0}^{\ell -1}{\Phi }^j\left(d_j\right)$ with an endomorphism $\Phi$ of an Abelian group. In such a numeral system, the $w$-NAF condition (each block of $w$ consecutive digits contains at most one nonzero) is shown to minimise the Hamming weight over all expansions with the same digit set if and only if it fulfills the subadditivity condition (the sum of every two expansions of weight $1$ admits an optimal $w$-NAF).

This result is then applied to imaginary quadratic bases, which are used for scalar multiplication in elliptic curve cryptography. Both an algorithmic criterion and generic answers for various cases are given. Imaginary quadratic integers of trace at least $3$ (in absolute value) have optimal $w$-NAFs for $w\ge 4$. The same holds for the special case of base $(\pm 3\pm \sqrt{-3})/2$ (four cases) and $w\ge 2$, which corresponds to Koblitz curves in characteristic three. In the case of $\tau =\pm 1\pm i$ (again four cases), optimality depends on the parity of $w$. Computational results for small trace are given.

Résumé

On étudie des systèmes de numération ${\sum }_{j=0}^{\ell -1}{\Phi }^j\left(D_j\right)$ avec un endomorphisme $\Phi$ d’un groupe abélien. On démontre que dans un tel système la condition $w$-NAF (chaque bloc de $w$ chiffres consécutifs contient au plus un chiffre non nul) minimise le poids de Hamming par rapport à toutes les représentations avec le même ensemble de chiffres si et seulement si la condition de sous-additivité est vérifiée (la somme de deux représentations de poids $1$ admet une représentation optimale $w$-NAF).

Ce résultat est ensuite appliqué sur les bases entières quadratiques complexes, qui sont utilisées pour la multiplication par un scalaire dans la cryptographie sur les courbes elliptiques. On présente un critère algorithmique et des réponses génériques pour des cas différents. Des entiers quadratiques complexes de trace au moins $3$ (en valeur absolue) admettent une $w$-NAF optimale pour $w\ge 4$. Il en va de même pour le cas particulier de la base $(\pm 3\pm \sqrt{-3})/2$ (quatre cas) et $w\ge 2$, qui correspond à des courbes de Koblitz en caractéristique trois. Dans le cas de $\tau =\pm 1\pm i$ (quatre cas), l’optimalité dépend de la parité de $w$. Des résultats numériques pour des traces plus petites sont présentés.

Détail

DOI : 10.5802/jtnb.840

Classification : 11A63, 94A60
Keywords: $\tau $-adic expansions, width-$w$ non-adjacent forms, redundant digit sets, elliptic curve cryptography, Koblitz curves, Frobenius endomorphism, scalar multiplication, Hamming weight, optimality, imaginary quadratic bases