<p>By a result of Chiu, Davida, and Litow [1], improved by Hesse, Allender, and Barrington [2], Chinese remainder representation base extension is computable in logarithmic space, and in fact in DLOGTIME-uniform $\mathrm{TC}^0$, when all the $p_i$ are “small” (i.e., given in unary). Since the effective size of the input is here $p^*+\sum_ip_i\le p^*+m\max_ip_i\le p^*+(\max_ip_i)^2$ (using the fact that the $p_i$ are distinct), this means it is computable in space
$$O\bigl(\max\{\log p^*,\log p_i:i=1,\dots,m\}\bigr).$$</p>

<p><strong>References:</strong></p>

<p>[1] A. Chiu, G. Davida, B. Litow, <a href="https://eudml.org/doc/92665" rel="nofollow noreferrer"><em>Division in logspace-uniform $\mathit{NC}^1$</em></a>, RAIRO – Theoretical Informatics and Applications 35 (2001), no. 3, pp. 259–275.</p>

<p>[2] W. Hesse, E. Allender, D. Mix Barrington, <a href="http://dx.doi.org/10.1016/S0022-0000(02)00025-9" rel="nofollow noreferrer"><em>Uniform constant-depth threshold circuits for division and iterated multiplication</em></a>, Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716.</p>

CC BY-SA 3.0
2016-11-07T16:57:51.443Z
In fact, recalling that the composition of two logspace functions is still logspace-computable (and in particular, does not require writing down the intermediate result): other results in the two papers show that reconstructing $x$ and computing $x\bmod p^*$ is still doable in logspace (and uniform $\mathrm{TC}^0$) when $p^*$ is an arbitrary integer given in binary. That is, one can do the computation in space $O(\max\{\log\log p^*,\log p_i:i=1,\dots,m\})$.
Emil Jeřábek
CC BY-SA 3.0
2016-11-10T17:42:23.193Z
Thanks, these references turned out to be very helpful to me.
mikero
CC BY-SA 3.0
2016-11-07T15:14:45.823Z
2016-11-07T15:14:45.823Z
Emil Jeřábek
<p>Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes if it helps).</p>

<p>I would like to compute $x \bmod{p^*}$ for some $p^* \not\in \{p_1, \ldots, p_m\}$, but with low space. </p>

<p>Of course I could reconstruct $x$ itself, but this would require $\log (\prod_i p_i) = \sum_i \log p_i$ bits of working space. Rather, I would like the computation to use something more like $\max_i \log p_i$ bits of space. Is this possible?</p>

<p>As a concrete example, suppose $\{ p_1, \ldots, p_m\}$ are the first $m$ primes and I would like to compute $x \bmod 4$. Or $\{ p_1, \ldots, p_m\}$ are the first $m$ <strong>odd</strong> primes, and I would like to compute $x \bmod 2$.</p>

<ds.algorithms><space-bounded>
Base extension in residue number systems with low space
mikero
# Base extension in residue number systems with low space

(Asked by: username_0 on 2016-11-03)

Suppose I have a number $x$ represented in a residue number system, so $x = (x\_1, \ldots, x\_m)$, where $x\_i \equiv x \pmod{p\_i}$, and the $p\_i$'s are all relatively prime (they can be distinct primes if it helps).

I would like to compute $x \bmod{p^\*}$ for some $p^\* \not\in \{p\_1, \ldots, p\_m\}$, but with low space.

Of course I could reconstruct $x$ itself, but this would require $\log (\prod\_i p\_i) = \sum\_i \log p\_i$ bits of working space. Rather, I would like the computation to use something more like $\max\_i \log p\_i$ bits of space. Is this possible?

As a concrete example, suppose $\{ p\_1, \ldots, p\_m\}$ are the first $m$ primes and I would like to compute $x \bmod 4$. Or $\{ p\_1, \ldots, p\_m\}$ are the first $m$ **odd** primes, and I would like to compute $x \bmod 2$.

**Tags:** ds.algorithms, space-bounded

---

## 1 answers

### Answer by username_1 on 2016-11-07. Score: 2 | Accepted answer

By a result of Chiu, Davida, and Litow [1], improved by Hesse, Allender, and Barrington [2], Chinese remainder representation base extension is computable in logarithmic space, and in fact in DLOGTIME-uniform $\mathrm{TC}^0$, when all the $p\_i$ are “small” (i.e., given in unary). Since the effective size of the input is here $p^\*+\sum\_ip\_i\le p^\*+m\max\_ip\_i\le p^\*+(\max\_ip\_i)^2$ (using the fact that the $p\_i$ are distinct), this means it is computable in space
$$O\bigl(\max\{\log p^\*,\log p\_i:i=1,\dots,m\}\bigr).$$

**References:**

[1] A. Chiu, G. Davida, B. Litow, [*Division in logspace-uniform $\mathit{NC}^1$*](https://eudml.org/doc/92665), RAIRO – Theoretical Informatics and Applications 35 (2001), no. 3, pp. 259–275.

[2] W. Hesse, E. Allender, D. Mix Barrington, [*Uniform constant-depth threshold circuits for division and iterated multiplication*](http://dx.doi.org/10.1016/S0022-0000(02)00025-9), Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716.

> **Comments:**
> **username_1**: In fact, recalling that the composition of two logspace functions is still logspace-computable (and in particular, does not require writing down the intermediate result): other results in the two papers show that reconstructing $x$ and computing $x\bmod p^*$ is still doable in logspace (and uniform $\mathrm{TC}^0$) when $p^*$ is an arbitrary integer given in binary. That is, one can do the computation in space $O(\max\{\log\log p^*,\log p_i:i=1,\dots,m\})$.  
> **username_0**: Thanks, these references turned out to be very helpful to me.  

---

