How quickly can we use Chinese remainder theorem to find a value? 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$.
 A: 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)$.
A: 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.  
