Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Modular exponentiation via the explicit Chinese remainder theorem

Authors: Daniel J. Bernstein and Jonathan P. Sorenson
Journal: Math. Comp. 76 (2007), 443-454
MSC (2000): Primary 11Y16; Secondary 68W10
Published electronically: September 14, 2006
MathSciNet review: 2261030
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Fix pairwise coprime positive integers $ p_1,p_2,\dots,p_s$. We propose representing integers $ u$ modulo $ m$, where $ m$ is any positive integer up to roughly $ \sqrt{p_1p_2\cdots p_s}$, as vectors $ (u\bmod p_1,u\bmod p_2,\dots,u\bmod p_s)$. We use this representation to obtain a new result on the parallel complexity of modular exponentiation: there is an algorithm for the Common CRCW PRAM that, given positive integers $ x$, $ e$, and $ m$ in binary, of total bit length $ n$, computes $ x^e\bmod m$ in time $ O(n/{\lg\lg n})$ using $ n^{O(1)}$ processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an $ O((\lg n)^3)$ expected time algorithm using $ \exp( O(\sqrt{n\lg n}))$ processors; von zur Gathen gave an NC algorithm for the highly special case that $ m$ is polynomially smooth.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 68W10

Retrieve articles in all journals with MSC (2000): 11Y16, 68W10

Additional Information

Daniel J. Bernstein
Affiliation: Department of Mathematics, Statistics, and Computer Science (M/C 249), The University of Illinois at Chicago, Chicago, IL 60607–7045

Jonathan P. Sorenson
Affiliation: Department of Computer Science and Software Engineering, Butler University, 4600 Sunset Avenue, Indianapolis, Indiana 46208

Received by editor(s): August 18, 2003
Received by editor(s) in revised form: June 15, 2005
Published electronically: September 14, 2006
Additional Notes: This paper combines and improves the preliminary papers \cite{1995/bernstein-mmecrt} by Bernstein and \cite{1999/sorenson} by Sorenson. Bernstein was supported by the National Science Foundation under grants DMS-9600083 and DMS–9970409. Sorenson was supported by the National Science Foundation under grant CCR–9626877. Sorenson completed part of this work while on sabbatical at Purdue University in Fall 1998.
Article copyright: © Copyright 2006 by the authors

American Mathematical Society