Modular exponentiation via the explicit Chinese remainder theorem

Bernstein, Daniel; Sorenson, Jonathan

doi:10.1090/S0025-5718-06-01849-7

Modular exponentiation via the explicit Chinese remainder theorem
HTML articles powered by AMS MathViewer

by Daniel J. Bernstein and Jonathan P. Sorenson;

Math. Comp. 76 (2007), 443-454

DOI: https://doi.org/10.1090/S0025-5718-06-01849-7

Published electronically: September 14, 2006

PDF

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

Leonard M. Adleman, Kireeti Kompella, Proceedings of the $20$th ACM symposium on theory of computing, Association for Computing Machinery, New York, 1988.
—, Using smoothness to achieve parallelism, in [1] (1988), 528–538.
Amod Agashe, Kristin Lauter, and Ramarathnam Venkatesan, Constructing elliptic curves with a known number of points over a prime field, High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Inst. Commun., vol. 41, Amer. Math. Soc., Providence, RI, 2004, pp. 1–17. MR 2075643
Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
Paul W. Beame, Stephen A. Cook, and H. James Hoover, Log depth circuits for division and related problems, SIAM J. Comput. 15 (1986), no. 4, 994–1003. MR 861365, DOI 10.1137/0215070
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.
Daniel J. Bernstein, Multidigit modular multiplication with the explicit Chinese remainder theorem, in [6] (1995). URL: http://cr.yp.to/papers.html#mmecrt.
Daniel J. Bernstein, Fast multiplication and its applications, to appear. URL: http://cr.yp. to/papers.html#multapps. ID 8758803e61822d485d54251b27b1a20d.
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.
A. Borodin and R. Moenck, Fast modular transforms, J. Comput. System Sci. 8 (1974), 366–386. MR 371144, DOI 10.1016/S0022-0000(74)80029-2
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Richard Cole and Uzi Vishkin, Faster optimal parallel prefix sums and list ranking, Inform. and Comput. 81 (1989), no. 3, 334–352. MR 1000070, DOI 10.1016/0890-5401(89)90036-9
Jean-Marc Couveignes, Computing a square root for the number field sieve, in [19] (1993), 95–102.
Shawna Meyer Eikenberry and Jonathan P. Sorenson, Efficient algorithms for computing the Jacobi symbol, J. Symbolic Comput. 26 (1998), no. 4, 509–523. MR 1646683, DOI 10.1006/jsco.1998.0226
John H. Reif (ed.), Synthesis of parallel algorithms, Morgan Kaufmann, San Mateo, CA, 1993. MR 1212591
Daniel M. Gordon, A survey of fast exponentiation methods, J. Algorithms 27 (1998), no. 1, 129–146. MR 1613189, DOI 10.1006/jagm.1997.0913
Richard M. Karp (chairman), $13$th annual symposium on switching and automata theory, IEEE Computer Society, Northridge, 1972.
Donald E. Knuth, The art of computer programming, volume $2$: seminumerical algorithms, 3rd edition, Addison-Wesley, Reading, 1997. ISBN 0-201-89684-2.
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, Berlin, 1993. MR 1321216, DOI 10.1007/BFb0091534
Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 1997. With a foreword by Ronald L. Rivest. MR 1412797
A. Borodin and R. Moenck, Fast modular transforms, J. Comput. System Sci. 8 (1974), 366–386. MR 371144, DOI 10.1016/S0022-0000(74)80029-2
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.
Peter L. Montgomery and Robert D. Silverman, An FFT extension to the $P-1$ factoring algorithm, Math. Comp. 54 (1990), no. 190, 839–854. MR 1011444, DOI 10.1090/S0025-5718-1990-1011444-3
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.
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
John H. Reif (ed.), Synthesis of parallel algorithms, Morgan Kaufmann, San Mateo, CA, 1993. MR 1212591
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Jonathan P. Sorenson, A sublinear-time parallel algorithm for integer modular exponentiation, in [24] (1999).
Jonathan Sorenson and Ian Parberry, Two fast parallel prime number sieves, Inform. and Comput. 114 (1994), no. 1, 115–130. MR 1294306, DOI 10.1006/inco.1994.1082
Larry Stockmeyer and Uzi Vishkin, Simulation of parallel random access machines by circuits, SIAM J. Comput. 13 (1984), no. 2, 409–422. MR 739997, DOI 10.1137/0213027
John H. Reif (ed.), Synthesis of parallel algorithms, Morgan Kaufmann, San Mateo, CA, 1993. MR 1212591
Alf van der Poorten and Andreas Stein (eds.), High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Institute Communications, vol. 41, American Mathematical Society, Providence, RI, 2004. Selected papers from the International Conference on Number Theory held in Banff, AB, May 24–30, 2003. MR 2070919, DOI 10.1090/fic/041
John H. Reif (ed.), Synthesis of parallel algorithms, Morgan Kaufmann, San Mateo, CA, 1993. MR 1212591
Joachim von zur Gathen, Computing powers in parallel, SIAM J. Comput. 16 (1987), no. 5, 930–945. MR 908877, DOI 10.1137/0216060