{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T04:49:17Z","timestamp":1778215757990,"version":"3.51.4"},"reference-count":35,"publisher":"American Mathematical Society (AMS)","issue":"257","license":[{"start":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T00:00:00Z","timestamp":1189728000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Fix pairwise coprime positive integers\n \n \n \n \n \n p<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n p<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u2026\n \n <\/mml:mo>\n ,<\/mml:mo>\n \n p<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n p_1,p_2,\\dots ,p_s<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We propose representing integers\n \n \n \n u<\/mml:mi>\n u<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n modulo\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , where\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is any positive integer up to roughly\n \n \n \n \n \n p<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n \n p<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n \n \u22ef\n \n <\/mml:mo>\n \n p<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n <\/mml:msqrt>\n \\sqrt {p_1p_2\\cdots p_s}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , as vectors\n \n \n \n \n (<\/mml:mo>\n u<\/mml:mi>\n mod<\/mml:mo>\n \n p<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n u<\/mml:mi>\n mod<\/mml:mo>\n \n p<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n \u2026\n \n <\/mml:mo>\n ,<\/mml:mo>\n u<\/mml:mi>\n mod<\/mml:mo>\n \n p<\/mml:mi>\n s<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n (u\\bmod p_1,u\\bmod p_2,\\dots ,u\\bmod p_s)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . 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\n \n \n \n x<\/mml:mi>\n x<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ,\n \n \n \n e<\/mml:mi>\n e<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in binary, of total bit length\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , computes\n \n \n \n \n \n x<\/mml:mi>\n e<\/mml:mi>\n <\/mml:msup>\n mod<\/mml:mo>\n m<\/mml:mi>\n <\/mml:mrow>\n x^e\\bmod m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n in time\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n \n lg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n lg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n O(n\/{\\lg \\lg n})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n using\n \n \n \n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n n^{O(1)}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n (<\/mml:mo>\n lg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n \n )<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n O((\\lg n)^3)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n expected time algorithm using\n \n \n \n \n exp<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n (<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n lg<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n \\exp ( O(\\sqrt {n\\lg n}))<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n processors; von zur Gathen gave an NC algorithm for the highly special case that\n \n \n \n m<\/mml:mi>\n m<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is polynomially smooth.\n <\/p>","DOI":"10.1090\/s0025-5718-06-01849-7","type":"journal-article","created":{"date-parts":[[2006,11,1]],"date-time":"2006-11-01T16:50:02Z","timestamp":1162399802000},"page":"443-454","source":"Crossref","is-referenced-by-count":25,"title":["Modular exponentiation via the explicit Chinese remainder theorem"],"prefix":"10.1090","volume":"76","author":[{"given":"Daniel","family":"Bernstein","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Sorenson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2006,9,14]]},"reference":[{"key":"1","unstructured":"Leonard M. Adleman, Kireeti Kompella, Proceedings of the 20th ACM symposium on theory of computing, Association for Computing Machinery, New York, 1988."},{"key":"2","doi-asserted-by":"crossref","unstructured":"\\bysame, Using smoothness to achieve parallelism, in [1] (1988), 528\u2013538.","DOI":"10.1145\/62212.62264"},{"key":"3","isbn-type":"print","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/fic\/041\/01","article-title":"Constructing elliptic curves with a known number of points over a prime field","author":"Agashe, Amod","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0821833537"},{"issue":"2","key":"4","doi-asserted-by":"publisher","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal, Manindra","year":"2004","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"issue":"4","key":"5","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0215070","article-title":"Log depth circuits for division and related problems","volume":"15","author":"Beame, Paul W.","year":"1986","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"6","unstructured":"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."},{"key":"7","unstructured":"Daniel J. Bernstein, Multidigit modular multiplication with the explicit Chinese remainder theorem, in [6] (1995). URL: \\url{http:\/\/cr.yp.to\/papers.html#mmecrt}."},{"key":"8","unstructured":"Daniel J. Bernstein, Fast multiplication and its applications, to appear. URL: \\url{http:\/\/cr.yp. to\/papers.html#multapps}. ID 8758803e61822d485d54251b27b1a20d."},{"key":"9","unstructured":"Daniel J. Bernstein, Pippenger\u2019s exponentiation algorithm, to be incorporated into author\u2019s High-speed cryptography book. URL: \\url{http:\/\/cr.yp.to\/papers.html#pippenger}."},{"key":"10","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/S0022-0000(74)80029-2","article-title":"Fast modular transforms","volume":"8","author":"Borodin, A.","year":"1974","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"key":"11","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"issue":"3","key":"12","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1016\/0890-5401(89)90036-9","article-title":"Faster optimal parallel prefix sums and list ranking","volume":"81","author":"Cole, Richard","year":"1989","journal-title":"Inform. and Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-5401","issn-type":"print"},{"key":"13","doi-asserted-by":"crossref","unstructured":"Jean-Marc Couveignes, Computing a square root for the number field sieve, in [19] (1993), 95\u2013102.","DOI":"10.1007\/BFb0091540"},{"issue":"4","key":"14","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1006\/jsco.1998.0226","article-title":"Efficient algorithms for computing the Jacobi symbol","volume":"26","author":"Meyer Eikenberry, Shawna","year":"1998","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"15","isbn-type":"print","volume-title":"Synthesis of parallel algorithms","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/155860135X"},{"issue":"1","key":"16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jagm.1997.0913","article-title":"A survey of fast exponentiation methods","volume":"27","author":"Gordon, Daniel M.","year":"1998","journal-title":"J. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/0196-6774","issn-type":"print"},{"key":"17","unstructured":"Richard M. Karp (chairman), 13th annual symposium on switching and automata theory, IEEE Computer Society, Northridge, 1972."},{"key":"18","unstructured":"Donald E. Knuth, The art of computer programming, volume 2: seminumerical algorithms, 3rd edition, Addison-Wesley, Reading, 1997. ISBN 0-201-89684-2."},{"key":"19","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0091534","volume-title":"The development of the number field sieve","volume":"1554","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540570136"},{"key":"20","series-title":"CRC Press Series on Discrete Mathematics and its Applications","isbn-type":"print","volume-title":"Handbook of applied cryptography","author":"Menezes, Alfred J.","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/0849385237"},{"key":"21","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/S0022-0000(74)80029-2","article-title":"Fast modular transforms","volume":"8","author":"Borodin, A.","year":"1974","journal-title":"J. Comput. System Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-0000","issn-type":"print"},{"key":"22","unstructured":"Peter L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph.D. thesis, University of California at Los Angeles, 1992. URL: \\url{http:\/\/cr.yp.to\/bib\/entries.html#1992\/montgomery}."},{"issue":"190","key":"23","doi-asserted-by":"publisher","first-page":"839","DOI":"10.2307\/2008514","article-title":"An FFT extension to the \ud835\udc43-1 factoring algorithm","volume":"54","author":"Montgomery, Peter L.","year":"1990","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"24","unstructured":"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\u201317,1999, book of preprints distributed at the conference, 1999."},{"key":"25","isbn-type":"print","volume-title":"Computational complexity","author":"Papadimitriou, Christos H.","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0201530821"},{"key":"26","isbn-type":"print","volume-title":"Synthesis of parallel algorithms","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/155860135X"},{"key":"27","first-page":"64","article-title":"Approximate formulas for some functions of prime numbers","volume":"6","author":"Rosser, J. Barkley","year":"1962","journal-title":"Illinois J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0019-2082","issn-type":"print"},{"key":"28","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"29","unstructured":"Jonathan P. Sorenson, A sublinear-time parallel algorithm for integer modular exponentiation, in [24] (1999)."},{"issue":"1","key":"30","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1006\/inco.1994.1082","article-title":"Two fast parallel prime number sieves","volume":"114","author":"Sorenson, Jonathan","year":"1994","journal-title":"Inform. and Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0890-5401","issn-type":"print"},{"issue":"2","key":"31","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0213027","article-title":"Simulation of parallel random access machines by circuits","volume":"13","author":"Stockmeyer, Larry","year":"1984","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"32","isbn-type":"print","volume-title":"Synthesis of parallel algorithms","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/155860135X"},{"key":"33","series-title":"Fields Institute Communications","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1090\/fic\/041","volume-title":"High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams","volume":"41","year":"2004","ISBN":"https:\/\/id.crossref.org\/isbn\/0821833537"},{"key":"34","isbn-type":"print","volume-title":"Synthesis of parallel algorithms","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/155860135X"},{"issue":"5","key":"35","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1137\/0216060","article-title":"Computing powers in parallel","volume":"16","author":"von zur Gathen, Joachim","year":"1987","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01849-7\/S0025-5718-06-01849-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01849-7\/S0025-5718-06-01849-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:46:48Z","timestamp":1776782808000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2007-76-257\/S0025-5718-06-01849-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,14]]},"references-count":35,"journal-issue":{"issue":"257","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["S0025-5718-06-01849-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-06-01849-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2006,9,14]]}}}