Modular exponentiation via the explicit Chinese remainder theorem

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.