Redundant Integer Representations and Fast Exponentiation

In this paper two modifications to the standard square and multiply method for exponentiation are discussed. The first, using a signed-digit representation of the exponent, has been examined previously by a number of authors, and we present a new precise and simple mathematical analysis of its performance. The second, a new technique, uses a different redundant representation of the exponent, which we call a string replacement representation; the performance of this new method is analysed and compared with previously proposed methods. The techniques considered in this paper have application in the implementation of cryptographic algorithms such as RSA, where modular exponentiations of very large integers need to be calculated.