High-radix and bit recoding techniques for modular exponentiation

Algorithms that make use of high-radix and bit recoding techniques to perform modular exponentiation are proposed. It is shown that the high-radix methods with optimal choice of the radix provide significant reductions in the number of multiplications required for modular exponentiation. It is then shown that bit recoding techniques similar to those used in binary multiplication algorithms can be used to further reduce the total number of multiplications. The algorithms presented are analyzed by counting the maximum and the average number of multiplications required.