High-radix and bit recoding techniques for modular exponentiation

1 January 1991

journal article
research article
Published by Taylor & Francis in International Journal of Computer Mathematics

Vol. 40 (3) , 139-156
https://doi.org/10.1080/00207169108804009

Abstract

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.

Keywords

This publication has 6 references indexed in Scilit:

A Fast Modular Multiplication Algorithm with Application to Two Key Cryptography
Published by Springer Nature ,1983
Fast decipherment algorithm for RSA public-key cryptosystem
Electronics Letters, 1982
An algorithm for modular exponentiation
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1981
An 0(n) Parallel Multiplier with Bit-Sequential Input and Output
IEEE Transactions on Computers, 1979
A method for obtaining digital signatures and public-key cryptosystems
Communications of the ACM, 1978
A SIGNED BINARY MULTIPLICATION TECHNIQUE
The Quarterly Journal of Mechanics and Applied Mathematics, 1951