Analysis of width- w non-adjacent forms to imaginary quadratic bases
Clemens Heuberger, Daniel Krenn · Journal of Number Theory · 2013
We consider digital expansions to the base of 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 non-adjacency condition. 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 (expectation, variance, central limit theorem). In the case of an imaginary quadratic τ and the digit set of minimal norm representatives, the analysis is much more refined. The proof follows Delangeʼs method. We also show that each element of Z[τ] has a w-NAF in that setting.