How quickly can we perform base extension in a residue number system?

Question

Thinking about residue number systems, one major operation is to extend the set of primes that a given value is modulated by, also known as base extension. For instance, a given number $N$ can be represented by a sequence of remainders or modulated values by another set of numbers, which are primes. We then have:

$$N = (n_0, n_1, \dots, n_m)$$

where

$$n_0 \equiv N \bmod p_0$$ $$n_1 \equiv N \bmod p_1$$ $$\dots$$

$$n_m \equiv N \bmod p_m$$

Suppose we have a new sequence of additional primes, $(p_{m+1}, p_{m+2}, \dots p_{m+q})$.

How quickly can we get the new sequence of remainders (or modulated values), $(n_{m+1}, n_{m+2}, \dots n_{m+q})$ for the same number, $N$, in the worst case?

Answer 1

Check out Lemma 4.4 in HesseAllenderBarrington - it may not be terribly useful for sequential complexity but says essentially that CRR (Chinese Remainder Representation) basis extension can be done in very uniform $\mathsf{TC}^0$. The exact bound is $\mathsf{FOM + POW} = \mathsf{FOM}$ (see also Corollary 6.2 of the same paper).