On τ-adic Representations of Integers

Elliptic curve cryptosystems have become increasingly popular due to their efficiency and the small size of the keys they use. Particularly, the anomalous curves introduced by Koblitz allow a complex representation of the keys, denoted τNAF, that make the computations over these curves more efficient. In this article, we propose an efficient method for randomizing a τNAF to produce different equivalent representations of the same key to the same complex base τ. We prove that the average Hamming density of the resulting representations is 0.5. We identify the pattern of the τNAFs yielding the maximum number of representations and the formula governing this number. We also present deterministic methods to compute the average and the exact number of possible representations of a τNAF.