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.

  • 2
    $\begingroup$ A Google search for parallel chinese remainder gives several hits that look highly relevant. Did you look at them? $\endgroup$ Oct 18, 2016 at 9:08
  • $\begingroup$ 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. $\endgroup$
    – caesar
    Oct 18, 2016 at 9:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.