How quickly can we use Chinese remainder theorem to find a value?

Question

If we have a value $x$ that is known modulo all primes less than $p$, how quickly can we determine its value?

In other words, we know $x \bmod 2$, $x \bmod 3$, $x \bmod 5$, etc... We also know that $x$ is a natural number or $0$, i.e. $x$ is not negative.. How quickly, asymptotically, can we determine $x$, assuming $x$ is uniquely determined by the set of primes used? I mean here that $x < 2 \cdot 3 \cdot 5 \cdot \cdots p$. I'm looking for bounds in terms of $p$.

Answer 1

The Chinese Remainder Theorem says that given relatively prime $\left\{p_i\right\}_{i=1}^n$ and any $\left\{x_i\right\}_{i=1}^n$ we can find an $x$ that satisfies $$ x\equiv x_i\pmod{p_i}\tag{1} $$ for all $i$ and that $x$ is unique mod $P=\prod\limits_{i=1}^np_i$.

To facilitate solving $(1)$ for each given $\left\{x_i\right\}_{i=1}^n$, we can compute $\left\{u_i\right\}_{i=1}^n$ so that $$ \begin{align} u_i&\equiv1\pmod{p_i}\\ u_i&\equiv0\pmod{P/p_i} \end{align}\tag{2} $$ by solving the equation $$ a_ip_i+b_iP/p_i=1\tag{3} $$ using the Extended Euclidean Algorithm, and setting $u_i=b_iP/p_i$.

Then, for any $\left\{x_i\right\}_{i=1}^n$, $$ x=\sum_{i=1}^nx_iu_i\tag{4} $$ satisfies $(1)$.

Answer 2

I have an equation for this. I'm not sure about the complexity or if it's unique and I use some awkward notation. But again we can't find a specific value for $x$ based on this information without all the primes, unless $p$ is the largest prime less than $x$ in which case those residues can't be chosen -- they are determined by the value for $x$. However, with $x < p\#$, I will oblige.

Let $x \equiv x_i\pmod{p_i}$ and $x_i \in [0, p_i)$

$$x \equiv \Sigma_{p_i<p}{\{x_i(\frac{p\#}{p_i})[(\frac{p\#}{p_i})^{-1}_{\pmod{p_i}}]\}} \pmod{p\#}$$

Because $p\# \equiv 0 \pmod{p_i}$ for all the primes less than $p$, $\frac{p\#}{p_i} \not \equiv 0 \pmod{p_i}$, and rings of integers mod primes have integer inverses,

$$ (\frac{p\#}{p_i})[(\frac{p\#}{p_i})^{-1}_{\pmod{p_i}}] \equiv 1 \pmod{p_i}$$ $$ (\frac{p\#}{p_i})[(\frac{p\#}{p_i})^{-1}_{\pmod{p_i}}] \equiv 0 \pmod{p_j}$$

where $p_j \ne p_i$ and both are less than $p$.

I want it to be clear that the inverse taken is from the ring of integers mod $p_i$. And therefore we've found $x$, conserving each residue.

Finding the inverse requires roughly i/2 steps, because the inverses are symmetric around (p+1)/2, and that step is carried out i times. And finding primorial is i steps, but that has to be done at the beginning, no matter what.

So $O(n + n^2/2)$ is my best guess for complexity.