# Parallel algorithm for Chinese remainder theorem

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.

• A Google search for parallel chinese remainder gives several hits that look highly relevant. Did you look at them? – David Richerby Oct 18 '16 at 9:08
• I did. There are several algorithms and that's why I posted my question here. There are algorithms that are based on the mixed radix system such as Garner's algorithm and others based on the conventional CRT reconstruction. I have no idea which can be more efficient especially if the execution platform is GPUs. – caesar Oct 18 '16 at 9:56