Modular exponentiation via the explicit Chinese remainder theorem

Daniel J. Bernstein
Jonathan P. Sorenson, Butler University

Abstract

In this paper we consider the problem of computing xe mod m for large integers x, e, and m. This is the bottleneck in Rabin’s algorithm for testing primality, the Diffie-Hellman algorithm for exchanging cryptographic keys, and many other common algorithms.