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.

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

| cite | improve this answer | |
  • $\begingroup$ 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\})$. $\endgroup$ – Emil Jeřábek Nov 7 '16 at 16:57
  • $\begingroup$ Thanks, these references turned out to be very helpful to me. $\endgroup$ – mikero Nov 10 '16 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.