Analysis of width-w non-adjacent forms to imaginary quadratic bases

Abstract. We consider digital expansions to the base of τ, where τ is an algebraic integer. For a w ≥ 2, the set of admissible digits consists of 0 and one representative of every residue class modulo τw which is not divisible by τ. 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 τ 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 Z[τ] 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