Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Minimality and other properties of the width-$w$ 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
Published electronically: July 12, 2005
MathSciNet review: 2176404
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

References [Enhancements On Off] (What's this?)

  • 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,
    Available from
  • 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,
  • 6. Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146. MR 1613189,
  • 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,
    Available from
  • 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,
  • 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,
  • 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
  • 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,

Similar Articles

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

Douglas R. Stinson
Affiliation: School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

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

American Mathematical Society