Analysis of Width-$w$ Non-Adjacent Forms to Imaginary Quadratic Bases

Abstract

We consider digital expansions to the base of $\tau$, where $\tau$ is an algebraic integer. For a $w\ge 2$, the set of admissible digits consists of 0 and one representative of every residue class modulo ${\tau }^w$ which is not divisible by $\tau$. The resulting redundancy is avoided by imposing the width $w$-NAF condition, i.e., in an expansion every block of $w$ consecutive digits contains at most one non-zero digit. Such constructs can be efficiently used in elliptic curve cryptography in conjunction with Koblitz curves. The present work deals with analysing the number of occurrences of a fixed non-zero digit. In the general setting, we study all $w$-NAFs of given length of the expansion. We give an explicit expression for the expectation and the variance of the occurrence of such a digit in all expansions. Further a central limit theorem is proved. In the case of an imaginary quadratic $\tau$ and the digit set of minimal norm representatives, the analysis is much more refined: We give an asymptotic formula for the number of occurrence of a digit in the $w$-NAFs of all elements of $\mathbb{Z}[\tau ]$ in some region (e.g. a disc). The main term coincides with the full block length analysis, but a periodic fluctuation in the second order term is also exhibited. The proof follows Delange's method. We also show that in the case of imaginary quadratic $\tau$ and $w\ge 2$, the digit set of minimal norm representatives leads to $w$-NAFs for \emph{all} elements of $\mathbb{Z}[\tau ]$. Additionally some properties of the fundamental domain are stated.

Cited by in corpus (3)

• Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases
• Existence and Optimality of $w$-Non-adjacent Forms with an Algebraic Integer Base
• Analysis of the Width-w Non-Adjacent Form in Conjunction with Hyperelliptic Curve Cryptography and with Lattices