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
DOI: https://doi.org/10.1090/S0025-5718-06-01849-7
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?)

  • 1. Leonard M. Adleman, Kireeti Kompella, Proceedings of the $ 20$th ACM symposium on theory of computing, Association for Computing Machinery, New York, 1988.
  • 2. -, Using smoothness to achieve parallelism, in [1] (1988), 528-538.
  • 3. Amod Agashe, Kristin Lauter, Ramarathnam Venkatesan, Constructing elliptic curves with a known number of points over a prime field, in [33] (2004), 1-17. URL: http://research.microsoft.com/~klauter/. MR 2005m:11112
  • 4. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in $ P$, Annals of Mathematics 160 (2004), 781-793. URL: http://ProjectEuclid.org/Dienst/UI/1.0/Summarize/euclid.annm/1111770735.MR 2123939 (2006a:11170)
  • 5. Paul W. Beame, Stephen A. Cook, H. James Hoover, Log depth circuits for division and related problems, SIAM Journal on Computing 15 (1986), 994-1003. ISSN 0097-5397. MR 0861365 (88b:68059)
  • 6. Daniel J. Bernstein, Detecting perfect powers in essentially linear time, and other studies in computational number theory, Ph.D. thesis, University of California at Berkeley, 1995.
  • 7. Daniel J. Bernstein, Multidigit modular multiplication with the explicit Chinese remainder theorem, in [6] (1995). URL: http://cr.yp.to/papers.html#mmecrt.
  • 8. Daniel J. Bernstein, Fast multiplication and its applications, to appear. URL: http://cr.yp. to/papers.html#multapps. ID 8758803e61822d485d54251b27b1a20d.
  • 9. Daniel J. Bernstein, Pippenger's exponentiation algorithm, to be incorporated into author's High-speed cryptography book. URL: http://cr.yp.to/papers.html#pippenger.
  • 10. Allan Borodin, Robert T. Moenck, Fast modular transforms, Journal of Computer and System Sciences 8 (1974), 366-386; older version, not a subset, in [21]. ISSN 0022-0000. URL: http://cr.yp.to/bib/entries.html#1974/borodin. MR 0371144 (51:7365)
  • 11. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathmatics, 138, Springer-Verlag, Berlin, 1993. ISBN 3-5440-55640-0. MR 1228206 (94i:11105)
  • 12. Richard Cole, Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Information and Computation 81 (1989), 334-352. ISSN 0890-5401. MR 1000070 (90k:68056)
  • 13. Jean-Marc Couveignes, Computing a square root for the number field sieve, in [19] (1993), 95-102. MR 13212222
  • 14. Shawna Meyer Eikenberry, Jonathan P. Sorenson, Efficient algorithms for computing the Jacobi symbol, Journal of Symbolic Computation 26 (1998), 509-523. ISSN 0747-7171. MR 1646683 (99h:11146)
  • 15. Faith E. Fich, The complexity of computation on the parallel random access machine, in [26] (1993), 843-899.MR 1212591 (94c:68086)
  • 16. Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms 27 (1998), 129-146. ISSN 0196-6774. URL: http://www.ccrwest.org/gordon/dan.html. MR 1613189 (99g:94014)
  • 17. Richard M. Karp (chairman), $ 13$th annual symposium on switching and automata theory, IEEE Computer Society, Northridge, 1972.
  • 18. Donald E. Knuth, The art of computer programming, volume $ 2$: seminumerical algorithms, 3rd edition, Addison-Wesley, Reading, 1997. ISBN 0-201-89684-2.
  • 19. Arjen K. Lenstra, Hendrik W. Lenstra, Jr. (editors), The development of the number field sieve, Lecture Notes in Mathematics, 1554, Springer-Verlag, Berlin, 1993. ISBN 3-540-57013-6. MR 1321216 (96m:11116)
  • 20. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of applied cryptography, CRC Press, Boca Raton, Florida, 1996. ISBN 0-8493-8523-7. URL: http://cacr.math.uwaterloo.ca/hac. MR 1412797 (99g:94015)
  • 21. Robert T. Moenck, Allan Borodin, Fast modular transforms via division, in [17] (1972), 90-96; newer version, not a superset, in [10]. URL: http://cr.yp.to/bib/entries.html#1972/moenck. MR 0371144 (51:7365)
  • 22. Peter L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph.D. thesis, University of California at Los Angeles, 1992. URL: http://cr.yp.to/bib/entries.html#1992/montgomery.
  • 23. Peter L. Montgomery, Robert D. Silverman, An FFT extension to the $ P-1$ factoring algorithm, Mathematics of Computation 54 (1990), 839-854. ISSN 0025-5718. MR 1011444 (90j:11142)
  • 24. Andrew M. Odlyzko, Gary Walsh, Hugh Williams (editors), Conference on the mathematics of public key cryptography: the Fields Institute for Research in the Mathematical Sciences, Toronto, Ontario, June $ 12$-$ 17, 1999$, book of preprints distributed at the conference, 1999.
  • 25. Christos M. Papadimitriou, Computational complexity, Addison-Wesley, Reading, Massachusetts, 1994. ISBN 0-201-53082-1. MR 1251285 (95f:68082)
  • 26. John H. Reif (editor), Synthesis of parallel algorithms, Morgan Kaufman, San Mateo, California, 1993. ISBN 1-55860-135-X. MR 1212591 (94c:68086)
  • 27. J. Barkley Rosser, Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois Journal of Mathematics 6 (1962), 64-94. ISSN 0019-2082. URL: http://cr.yp.to/bib/entries.html#1962/rosser. MR 0137689 (25:1139)
  • 28. Arnold Schönhage, Volker Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292. ISSN 0010-485X. URL: http://cr.yp.to/bib/entries.html#1971/schoenhage-mult. MR 0292344 (45:1431)
  • 29. Jonathan P. Sorenson, A sublinear-time parallel algorithm for integer modular exponentiation, in [24] (1999).
  • 30. Jonathan P. Sorenson, Ian Parberry, Two fast parallel prime number sieves, Information and Computation 144 (1994), 115-130. ISSN 0890-5401. MR 1294306 (95h:11097)
  • 31. Larry Stockmeyer, Uzi Vishkin, Simulation of parallel random access machines by circuits, SIAM Journal on Computing 13 (1984), 409-422. ISSN 0097-5397. MR 0739997 (85g:68018)
  • 32. Stephen R. Tate, Newton iteration and integer division, in [26] (1993), 539-572. MR 1212591 (94c:68086)
  • 33. Alf van der Poorten, Andreas Stein (editors), High primes and misdemeanours: lectures in honour of the $ 60$th birthday of Hugh Cowie Williams, American Mathematical Society, Providence, 2004. ISBN 0-8218-3353-7. MR 2005b:11003
  • 34. Uzi Vishkin, Advanced parallel prefix-sums, list ranking and connectivity, in [26] (1993), 215-257.MR 1212591 (94c:68086)
  • 35. Joachim von zur Gathen, Computing powers in parallel, SIAM Journal on Computing 16 (1987), 930-945. MR 0908877 (89j:68060)

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
Email: djb@cr.yp.to

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

DOI: https://doi.org/10.1090/S0025-5718-06-01849-7
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