Optimality of the Width-w Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases
Journal de théorie des nombres de Bordeaux, Volume 25 (2013) no. 2, p. 353-386

We consider digit expansions j=0 -1 Φ j (d j ) with an endomorphism Φ 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 w4. The same holds for the special case of base (±3±-3)/2 (four cases) and w2, which corresponds to Koblitz curves in characteristic three. In the case of τ=±1±i (again four cases), optimality depends on the parity of w. Computational results for small trace are given.

On étudie des systèmes de numération j=0 -1 Φ j (D j ) avec un endomorphisme Φ 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 w4. Il en va de même pour le cas particulier de la base (±3±-3)/2 (quatre cas) et w2, qui correspond à des courbes de Koblitz en caractéristique trois. Dans le cas de τ=±1±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.

DOI : https://doi.org/10.5802/jtnb.840
Classification:  11A63,  94A60
Keywords: τ-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
     author = {Heuberger, Clemens and Krenn, Daniel},
     title = {Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {25},
     number = {2},
     year = {2013},
     pages = {353-386},
     doi = {10.5802/jtnb.840},
     mrnumber = {3228312},
     zbl = {1282.11005},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2013__25_2_353_0}
Heuberger, Clemens; Krenn, Daniel. Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases. Journal de théorie des nombres de Bordeaux, Volume 25 (2013) no. 2, pp. 353-386. doi : 10.5802/jtnb.840. http://www.numdam.org/item/JTNB_2013__25_2_353_0/

[1] Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger, Minimality of the Hamming weight of the τ-NAF for Koblitz curves and improved combination with point halving. Selected Areas in Cryptography: 12th International Workshop, SAC 2005, Kingston, ON, Canada, August 11–12, 2005, Revised Selected Papers (B. Preneel and S. Tavares, eds.), Lecture Notes in Comput. Sci., vol. 3897, Springer, Berlin, 2006, pp. 332–344. | MR 2241647 | Zbl 1151.94474

[2] —, Scalar multiplication on Koblitz curves. Using the Frobenius endomorphism and its combination with point halving: Extensions and mathematical analysis. Algorithmica 46 (2006), 249–270. | MR 2291956 | Zbl 1106.94021

[3] —, Arithmetic of supersingular Koblitz curves in characteristic three. Tech. Report 2010-8, Graz University of Technology, 2010, http://www.math.tugraz.at/fosp/pdfs/tugraz_0166.pdf, also available as Cryptology ePrint Archive, Report 2010/436, http://eprint.iacr.org/.

[4] Roberto Maria Avanzi, A Note on the Signed Sliding Window Integer Recoding and a Left-to-Right Analogue. Selected Areas in Cryptography: 11th International Workshop, SAC 2004, Waterloo, Canada, August 9-10, 2004, Revised Selected Papers (H. Handschuh and A. Hasan, eds.), Lecture Notes in Comput. Sci., vol. 3357, Springer-Verlag, Berlin, 2004, pp. 130–143. | MR 2180673 | Zbl 1117.94007

[5] Ian F. Blake, V. Kumar Murty, and Guangwu Xu, Efficient algorithms for Koblitz curves over fields of characteristic three. J. Discrete Algorithms 3 (2005), no. 1, 113–124. | MR 2167767 | Zbl 1070.11056

[6] —, A note on window τ-NAF algorithm. Inform. Process. Lett. 95 (2005), 496–502. | MR 2155136

[7] —, Nonadjacent radix-τ expansions of integers in Euclidean imaginary quadratic number fields. Canad. J. Math. 60 (2008), no. 6, 1267–1282. | MR 2462447 | Zbl 1228.11160

[8] László Germán and Attila Kovács, On number system constructions. Acta Math. Hungar. 115 (2007), no. 1-2, 155–167. | MR 2316627 | Zbl 1153.11003

[9] Daniel M. Gordon, A survey of fast exponentiation methods. J. Algorithms 27 (1998), 129–146. | MR 1613189 | Zbl 0915.11064

[10] Clemens Heuberger, Redundant τ-adic expansions II: Non-optimality and chaotic behaviour. Math. Comput. Sci. 3 (2010), 141–157. | MR 2608292 | Zbl 1205.11014

[11] Clemens Heuberger and Daniel Krenn, Analysis of width-w non-adjacent forms to imaginary quadratic bases. J. Number Theory 133 (2013), 1752–1808. | MR 3007130 | Zbl pre06139698

[12] Clemens Heuberger and Helmut Prodinger, Analysis of alternative digit sets for nonadjacent representations. Monatsh. Math. 147 (2006), 219–248. | MR 2215565 | Zbl 1094.11007

[13] Thomas W. Hungerford, Algebra. Graduate Texts in Mathematics, vol. 73, Springer, 1996. | MR 600654 | Zbl 0442.00002

[14] Jonathan Jedwab and Chris J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation. Electron. Lett. 25 (1989), 1171–1172. | Zbl 0709.94699

[15] Donald E. Knuth, Seminumerical algorithms. third ed., The Art of Computer Programming, vol. 2, Addison-Wesley, 1998. | MR 633878 | Zbl 0895.65001

[16] Neal Koblitz, CM-curves with good cryptographic properties. Advances in cryptology—CRYPTO ’91 (Santa Barbara, CA, 1991) (J. Feigenbaum, ed.), Lecture Notes in Comput. Sci., vol. 576, Springer, Berlin, 1992, pp. 279–287. | MR 1243654 | Zbl 0780.14018

[17] —, An elliptic curve implementation of the finite field digital signature algorithm. Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998), Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 327–337. | MR 1670960

[18] Markus Kröll, Optimality of digital expansions to the base of the Frobenius endomorphism on Koblitz curves in characteristic three. Tech. Report 2010-09, Graz University of Technology, 2010, available athttp://www.math.tugraz.at/fosp/pdfs/tugraz_0167.pdf.

[19] M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. | MR 1905123 | Zbl 1001.68093

[20] Willi Meier and Othmar Staffelbach, Efficient multiplication on certain nonsupersingular elliptic curves. Advances in cryptology—CRYPTO ’92 (Santa Barbara, CA, 1992) (Ernest F. Brickell, ed.), Lecture Notes in Comput. Sci., vol. 740, Springer, Berlin, 1993, pp. 333–344. | MR 1287863 | Zbl 0817.94015

[21] James A. Muir and Douglas R. Stinson, New minimal weight representations for left-to-right window methods. Topics in Cryptology — CT-RSA 2005 The Cryptographers’ Track at the RSA Conference 2005, San Francisco, CA, USA, February 14–18, 2005, Proceedings (A. J. Menezes, ed.), Lecture Notes in Comput. Sci., vol. 3376, Springer, Berlin, 2005, pp. 366–384. | MR 2174389 | Zbl 1079.94566

[22] —, Minimality and other properties of the width-w nonadjacent form. Math. Comp. 75 (2006), 369–384. | MR 2176404

[23] Braden Phillips and Neil Burgess, Minimal weight digit set conversions. IEEE Trans. Comput. 53 (2004), 666–677.

[24] George W. Reitwiesner, Binary arithmetic. Advances in computers, vol. 1, Academic Press, New York, 1960, pp. 231–308. | MR 122018

[25] Jerome A. Solinas, An improved algorithm for arithmetic on a family of elliptic curves. Advances in Cryptology — CRYPTO ’97. 17th annual international cryptology conference. Santa Barbara, CA, USA. August 17–21, 1997. Proceedings (B. S. Kaliski, jun., ed.), Lecture Notes in Comput. Sci., vol. 1294, Springer, Berlin, 1997, pp. 357–371. | Zbl 1032.11062

[26] —, Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19 (2000), 195–249. | MR 1759617 | Zbl 0997.94017

[27] William A. Stein et al., Sage Mathematics Software (Version 4.7.1). The Sage Development Team, 2011, http://www.sagemath.org.

[28] Christiaan van de Woestijne, The structure of Abelian groups supporting a number system (extended abstract). Actes des rencontres du CIRM 1 (2009), no. 1, 75–79.