Analysis of width-\(w\) non-adjacent forms to imaginary quadratic bases (Q1937312)

Let \(\tau\in \mathbb C\) be an algebraic integer and let the block length \(w\geq 2\) be given. Let the digit set \(\mathcal D\) consist of minimal norm representatives of residue classes modulo \(\tau^w\) in \(\mathbb Z[\tau]\) that do not divide \(\tau\). Now let \(z\in \mathbb Z[\tau]\) with \[ z=\sum_{j=0}^{\ell-1} z_j \tau^j. \] Such an expansion is a width-\(w\) \(\tau\)-adic non-adjacent form, or \(w\)-NAF for short, if each block of \(w\) consecutive digits \(z_j,\dots,z_{j+w-1}\) contains at most one non-zero digit. In view of cryptographic applications the case that \(\tau\) is an imaginary quadratic integer is of special interest. Therefore the authors assume that \(\tau\) is a solution of an equation \(\tau^2-p\tau+q\) with \(p,q\in \mathbb Z\) and \(4q-p^2>0\). The authors give a complete analysis of the \(w\)-NAFs. In section 5 they count the number of \(w\)-NAFs of length \(n\) (Theorem 5.1) and consider the distribution of the digits of \(w\)-NAFs of fixed length \(n\) (Theorem 5.1). In section 7 an algorithm to compute \(w\)-NAFs is given. Moreover the authors prove the existence and the uniqueness of \(w\)-NAF expansions (Theorem 7.1). Finally in section 11 the number of occurrences of a nonzero digit in a region of \(\mathbb C\) is considered (Theorem 11.1).