# Base extension in residue number systems with low space

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$.

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).$$
[1] A. Chiu, G. Davida, B. Litow, Division in logspace-uniform $\mathit{NC}^1$, RAIRO – Theoretical Informatics and Applications 35 (2001), no. 3, pp. 259–275.
• 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 Nov 7 '16 at 16:57