Minimality and other properties of the width-$w$ nonadjacent form

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,\pm 1\}$ 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.