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

References:

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

[2] W. Hesse, E. Allender, D. Mix Barrington, Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716.