What is the most efficient (in terms of running time) algorithm that solves the Chinese remainder theorem (CRT) on a set of integer residues. That is, given a set of moduli $\{m_i\}_{i=1}^{r}$ and set of residues $\{x_i\}_{i=1}^{r}$ such that $X \equiv x_i~mod~m_i$, find $X \in \mathbb{Z}_M$ where $M=\prod_{i=1}^{r}m_i$.Are there any parallel algorithms to calculate $X$?If there is a parallel algorithm, how does it account for large values of $X$ that can exceed the underlying computing machine word length?Pointers to relevant resources are appreciated.
Parallel algorithm for Chinese remainder theorem
reference request;parallel computing;numerical algorithms;modular arithmetic