Minimality and other properties of the width- nonadjacent form

Authors:
James A. Muir and Douglas R. Stinson

Journal:
Math. Comp. **75** (2006), 369-384

MSC (2000):
Primary 94A60, 11T71, 14G50; Secondary 94B40

DOI:
https://doi.org/10.1090/S0025-5718-05-01769-2

Published electronically:
July 12, 2005

MathSciNet review:
2176404

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be an integer and let be the set of integers that includes zero and the odd integers with absolute value less than . Every integer can be represented as a finite sum of the form , with , such that of any consecutive 's at most one is nonzero. Such representations are called *width- nonadjacent forms* (-NAFs). When these representations use the digits and coincide with the well-known *nonadjacent forms*. Width- nonadjacent forms are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. We provide some new results on the -NAF. We show that -NAFs have a minimal number of nonzero digits and we also give a new characterization of the -NAF in terms of a (right-to-left) lexicographical ordering. We also generalize a result on -NAFs and show that any base 2 representation of an integer, with digits in , that has a minimal number of nonzero digits is at most one digit longer than its binary representation.

**1.**R. M. Avanzi.

A Note on the Sliding Window Integer Recoding and its Left-to-Right Analogue,

to appear in ``Workshop on Selected Areas in Cryptography - SAC 2004''.**2.**I. F. Blake, G. Seroussi, and N. P. Smart,*Elliptic curves in cryptography*, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR**1771549****3.**S. H. Chang and N. Tsao-Wu.

Distance and Structure of Cyclic Arithmetic Codes,

in ``Proceedings of the Hawaii International Conference on System Sciences'' (1968), 463-466.**4.**H. Cohen.

Analysis of the Flexible Window Powering Algorithm,

Preprint.

Available from`http://www.math.u-bordeaux.fr/~cohen/window.dvi`

.**5.**Henri Cohen, Atsuko Miyaji, and Takatoshi Ono,*Efficient elliptic curve exponentiation using mixed coordinates*, Advances in cryptology—ASIACRYPT’98 (Beijing), Lecture Notes in Comput. Sci., vol. 1514, Springer, Berlin, 1998, pp. 51–65. MR**1726152**, https://doi.org/10.1007/3-540-49649-1_6**6.**Daniel M. Gordon,*A survey of fast exponentiation methods*, J. Algorithms**27**(1998), no. 1, 129–146. MR**1613189**, https://doi.org/10.1006/jagm.1997.0913**7.**Darrel Hankerson, Alfred Menezes, and Scott Vanstone,*Guide to elliptic curve cryptography*, Springer Professional Computing, Springer-Verlag, New York, 2004. MR**2054891****8.**C. Heuberger, R. Katti, H. Prodinger and X. Ruan.

The Alternating Greedy Expansion and Applications to Left-to-Right Algorithms in Cryptography,

Preprint.

Available from`http://www.wits.ac.za/helmut/paperlst.htm`

.**9.**Kenji Koyama and Yukio Tsuruoka,*Speeding up elliptic cryptosystems by using a signed binary window method*, Advances in cryptology—CRYPTO ’92 (Santa Barbara, CA, 1992) Lecture Notes in Comput. Sci., vol. 740, Springer, Berlin, 1993, pp. 345–357. MR**1287864**, https://doi.org/10.1007/3-540-48071-4_25**10.**J. H. van Lint,*Introduction to coding theory*, 3rd ed., Graduate Texts in Mathematics, vol. 86, Springer-Verlag, Berlin, 1999. MR**1664228****11.**A. Miyaji, T. Ono and H. Cohen.

Efficient Elliptic Curve Exponentiation,

in ``Information and Communication Security - ICICS '97'',*Lecture Notes in Computer Science***1334**(1997), 282-290.**12.**Bodo Möller,*Improved techniques for fast exponentiation*, Information security and cryptology—ICISC 2002, Lecture Notes in Comput. Sci., vol. 2587, Springer, Berlin, 2003, pp. 298–312. MR**2080830**, https://doi.org/10.1007/3-540-36552-4_21**13.**J. A. Muir and D. R. Stinson.

New Minimal Weight Representations for Left-to-Right Window Methods,

Technical Report CORR 2004-19, Centre for Applied Cryptographic Research.

Available from`http://www.cacr.math.uwaterloo.ca/techreports/2004`.**14.**K. Okeya, K. Schmidt-Samoa, C. Spahn and T. Takagi.

Signed Binary Representations Revisited,

in ``Advances in Cryptology - CRYPTO 2004'',*Lecture Notes in Computer Science***3152**(2004), 123-139.**15.**George W. Reitwiesner,*Binary arithmetic*, Advances in computers, Vol. 1, Academic Press, New York, 1960, pp. 231–308. MR**0122018****16.**Jerome A. Solinas,*Efficient arithmetic on Koblitz curves*, Des. Codes Cryptogr.**19**(2000), no. 2-3, 195–249. Towards a quarter-century of public key cryptography. MR**1759617**, https://doi.org/10.1023/A:1008306223194

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
94A60,
11T71,
14G50,
94B40

Retrieve articles in all journals with MSC (2000): 94A60, 11T71, 14G50, 94B40

Additional Information

**James A. Muir**

Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Email:
jamuir@uwaterloo.ca

**Douglas R. Stinson**

Affiliation:
School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Email:
dstinson@uwaterloo.ca

DOI:
https://doi.org/10.1090/S0025-5718-05-01769-2

Keywords:
Efficient representations,
minimal weight,
elliptic curve arithmetic

Received by editor(s):
March 29, 2004

Received by editor(s) in revised form:
August 21, 2004

Published electronically:
July 12, 2005

Additional Notes:
The second author is supported by NSERC grant RGPIN 203114-02.

Article copyright:
© Copyright 2005
American Mathematical Society