1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ A Google search for parallel chinese remainder gives several hits that look highly relevant. Did you look at them? $\endgroup$
    – David Richerby
    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

0

Reset to default

Your Answer

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