"Modular exponentiation via the explicit Chinese remainder theorem" by Daniel J Bernstein

Selected Works of Jon Sorenson

Follow Contact

Article

Modular exponentiation via the explicit Chinese remainder theorem

Mathematics of Computation

Daniel J Bernstein
Jonathan P Sorenson, Butler University

Download Find in your library

Document Type

Article

Publication Date

1-1-2007

Disciplines

Applied Mathematics,
Computer Sciences and
Theory and Algorithms

DOI

http://dx.doi.org/10.1090/S0025-5718-06-01849-7

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.

Rights

This is an electronic copy of an article originally publishing in Mathematics of Computation. Archived with permission. The author(s) reserves all rights.

Citation Information

Daniel J. Bernstein and Jonathan P. Sorenson. "Modular exponentiation via the explicit Chinese remainder theorem" Mathematics of Computaion 76.257 (2007): 443-454.