Redundant integer representations and fast exponentiation (Q1910428)

Efficient implementation of modular exponentiation of large integers is of great significance for many cryptographic algorithms. The well-known ``square and multiply'' technique seems to be generally accepted, yet the number of multiplications involved can be reduced using alternative representation of the exponent. The paper deals with two such representations. In the first case use of signed-digit representations of the exponent already proposed by other authors is considered and a precise analysis of its performance is given. Next, a new technique based on a different redundant representation of the exponent, called string replacement, is proposed and its complexity analyzed. Finally the new algorithm is compared with other variants of the square-and-multiply exponentiation algorithm.