How quickly can we perform base extension in a residue number system? 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?
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).