TY - JOUR

T1 - Modular exponentiation via the explicit Chinese remainder theorem

AU - Bernstein, D.J.

AU - Sorenson, J.P.

PY - 2007

Y1 - 2007

N2 - Fix pairwise coprime positive integers . We propose representing integers modulo , where is any positive integer up to roughly , as vectors . 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 , , and in binary, of total bit length , computes in time using processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an expected time algorithm using processors; von zur Gathen gave an NC algorithm for the highly special case that is polynomially smooth.

AB - Fix pairwise coprime positive integers . We propose representing integers modulo , where is any positive integer up to roughly , as vectors . 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 , , and in binary, of total bit length , computes in time using processors. For comparison, a parallelization of the standard binary algorithm takes superlinear time; Adleman and Kompella gave an expected time algorithm using processors; von zur Gathen gave an NC algorithm for the highly special case that is polynomially smooth.

U2 - 10.1090/S0025-5718-06-01849-7

DO - 10.1090/S0025-5718-06-01849-7

M3 - Article

VL - 76

SP - 443

EP - 454

JO - Mathematics of Computation

JF - Mathematics of Computation

SN - 0025-5718

ER -