Random Digit Representation of Integers

Modular exponentiation is core to today’s main stream public key cryptographic systems. In this article, we generalize the classical fractional wNAF method for modular exponentiation – the classical method uses a digit set of the form {1, 3,...,m} which is extended here to any set of odd integers of the form {1, d2,..., dn}. We give a formula for the average density of non-zero terms in this new representation and discuss its asymptotic behavior when those digits are randomly chosen from a given set. We also propose a specific method for the precomputation phase of the exponentiation algorithm.