Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
S. Arno and F. S. Wheeler, Signed digit representations of minimal Hamming weight, IEEE Transactions on Computers, Vol. 42 (1993) pp. 1007–1010.
H. J. Beker and F. C. Piper, Cipher Systems, Van Nostrand Reinhold (1982).
A. D. Booth, A signed binary multiplication technique, Quarterly Journal of Mechanics and Applied Mathematics, Vol. 4 (1951) pp. 236–240.
E. F. Brickell, A fast modular multiplication algorithm with application to two key cryptography, Advances in Cryptology, Proceedings of Crypto '82 (1982) pp. 51–60.
O. Egecioglu and C. K. Koc, Fast modular exponentiation, Proceedings of 1990 Bilkent International Conference on New Trends in Communication, Control, and Signal Processing, Elsevier Science Publishing Co., Ankara Turkey (1990) pp. 188–194.
L.C. K. Hui and K. Y. Lam, Fast square and multiply exponentiation for RSA, Electronics Letters, Vol. 30 (1994) pp. 1396–1397.
J. Jedwab and C. J. Mitchell, Minimum weight modified signed digit representations and fast exponentiation, Electronic Letters, Vol. 25 (1989) pp. 1171–1172.
D. E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms, 2nd edition, Addison-Wesley, Reading, Mass. (1981).
C. K. Koc. High-radix and bit recoding techniques for modular exponentiation. International Journal of Computer Mathematics, Vol. 40 (1991) pp. 139–156.
C. K. Koc and C. Y. Hung, Adaptive m-ary segmentation and canonical recoding algorithms for multiplication of large binary numbers, Computers Math. Applic., Vol. 24 (1992) pp. 312.
P. L. Montgomery, Modular multiplication without trial division, Mathematics of Computation, Vol. 44 (1985) pp. 519–521.
M. J. Norris and G. J. Simmons, Algorithms for high-speed modular arithmetics. Congressus Numerantium, Vol. 31 (1981) pp. 151–163.
K. C. Posch and R. Posch, Modulo reduction in residue number systems, IEEE Transactions on Parallel and Distributed Systems, Vol. 6 (1995) pp. 449–454.
J.–J. Quisquater and C. Couvreur, Fast decipherment algorithm for RSA public-key cryptosystem, Electronic Letters, Vol. 18 (1982) pp. 905–907.
G. W. Reitwiesner, Binary arithmetic, Advances in Computers I, (F. L. Alt ed.), Academic, New York (1960) pp. 232–308.
R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, Vol. 21 (1978) pp. 120–126.
A. Selby and C. Mitchell, Algorithms for software implementations of RSA, Proceedings of the IEE. Part E, Vol. 136 (1989) pp. 166–170.
N. Takagi and S. Yajima, Modular multiplication hardware algorithms with a redundant representation and their application to RSA cryptosystem, IEEE Transactions on Computers, Vol. 41 (1992) pp. 887–891.
N. Takagi, H. Yasuura, and S. Yajima, High-speed VLSI multiplication algorithm with a redundant binary addition tree, IEEE transactions on Computers, Vol. C-34 (1985) pp. 789–796.
C. N. Zhang, An improved binary algorithm for RSA, Computers Math. Applic., Vol. 25 (1993) pp. 15–24.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gollmann, D., Han, Y. & Mitchell, C.J. Redundant Integer Representations and Fast Exponentiation. Designs, Codes and Cryptography 7, 135–151 (1996). https://doi.org/10.1023/A:1018013116103
Issue Date:
DOI: https://doi.org/10.1023/A:1018013116103