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

Clemens Heuberger^{[1]}; Daniel Krenn^{[2]}

- [1] Institute of Mathematics Alpen-Adria-Universität Klagenfurt Universitätsstraße 65–67, 9020 Klagenfurt am Wörthersee, Austria
- [2] 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 (2013)

- Volume: 25, Issue: 2, page 353-386
- ISSN: 1246-7405

## Access Full Article

top## Abstract

top## How to cite

topHeuberger, Clemens, and 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 25.2 (2013): 353-386. <http://eudml.org/doc/275784>.

@article{Heuberger2013,

abstract = {We consider digit expansions $\sum _\{j=0\}^\{\ell -1\} \Phi ^j(d_j)$ 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.},

affiliation = {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},

author = {Heuberger, Clemens, Krenn, Daniel},

journal = {Journal de Théorie des Nombres de Bordeaux},

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; -adic expansions; width- non-adjacent forms},

language = {eng},

month = {9},

number = {2},

pages = {353-386},

publisher = {Société Arithmétique de Bordeaux},

title = {Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases},

url = {http://eudml.org/doc/275784},

volume = {25},

year = {2013},

}

TY - JOUR

AU - Heuberger, Clemens

AU - Krenn, Daniel

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

JO - Journal de Théorie des Nombres de Bordeaux

DA - 2013/9//

PB - Société Arithmétique de Bordeaux

VL - 25

IS - 2

SP - 353

EP - 386

AB - We consider digit expansions $\sum _{j=0}^{\ell -1} \Phi ^j(d_j)$ 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.

LA - eng

KW - $\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; -adic expansions; width- non-adjacent forms

UR - http://eudml.org/doc/275784

ER -

## References

top- Roberto Avanzi, Clemens Heuberger, and Helmut Prodinger, Minimality of the Hamming weight of the $\tau $-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. Zbl1151.94474MR2241647
- —, Scalar multiplication on Koblitz curves. Using the Frobenius endomorphism and its combination with point halving: Extensions and mathematical analysis. Algorithmica 46 (2006), 249–270. Zbl1106.94021MR2291956
- —, 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/.
- 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. Zbl1117.94007MR2180673
- 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. Zbl1070.11056MR2167767
- —, A note on window $\tau $-NAF algorithm. Inform. Process. Lett. 95 (2005), 496–502. MR2155136
- —, Nonadjacent radix-$\tau $ expansions of integers in Euclidean imaginary quadratic number fields. Canad. J. Math. 60 (2008), no. 6, 1267–1282. Zbl1228.11160MR2462447
- László Germán and Attila Kovács, On number system constructions. Acta Math. Hungar. 115 (2007), no. 1-2, 155–167. Zbl1153.11003MR2316627
- Daniel M. Gordon, A survey of fast exponentiation methods. J. Algorithms 27 (1998), 129–146. Zbl0915.11064MR1613189
- Clemens Heuberger, Redundant $\tau $-adic expansions II: Non-optimality and chaotic behaviour. Math. Comput. Sci. 3 (2010), 141–157. Zbl1205.11014MR2608292
- Clemens Heuberger and Daniel Krenn, Analysis of width-$w$ non-adjacent forms to imaginary quadratic bases. J. Number Theory 133 (2013), 1752–1808. Zbl1300.11013MR3007130
- Clemens Heuberger and Helmut Prodinger, Analysis of alternative digit sets for nonadjacent representations. Monatsh. Math. 147 (2006), 219–248. Zbl1094.11007MR2215565
- Thomas W. Hungerford, Algebra. Graduate Texts in Mathematics, vol. 73, Springer, 1996. Zbl0442.00002MR600654
- Jonathan Jedwab and Chris J. Mitchell, Minimum weight modified signed-digit representations and fast exponentiation. Electron. Lett. 25 (1989), 1171–1172. Zbl0709.94699
- Donald E. Knuth, Seminumerical algorithms. third ed., The Art of Computer Programming, vol. 2, Addison-Wesley, 1998. Zbl0895.65001MR633878
- 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. Zbl0780.14018MR1243654
- —, 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. MR1670960
- 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.
- M. Lothaire, Algebraic combinatorics on words. Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002. Zbl1001.68093MR1905123
- 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. Zbl0817.94015MR1287863
- 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. Zbl1079.94566MR2174389
- —, Minimality and other properties of the width-$w$ nonadjacent form. Math. Comp. 75 (2006), 369–384. Zbl1091.94026MR2176404
- Braden Phillips and Neil Burgess, Minimal weight digit set conversions. IEEE Trans. Comput. 53 (2004), 666–677.
- George W. Reitwiesner, Binary arithmetic. Advances in computers, vol. 1, Academic Press, New York, 1960, pp. 231–308. MR122018
- 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. Zbl1032.11062
- —, Efficient arithmetic on Koblitz curves. Des. Codes Cryptogr. 19 (2000), 195–249. Zbl0997.94017MR1759617
- William A. Stein et al., Sage Mathematics Software (Version 4.7.1). The Sage Development Team, 2011, http://www.sagemath.org.
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.