<p>Check out Lemma 4.4 in <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.8928" rel="nofollow">HesseAllenderBarrington</a> - 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).</p>

CC BY-SA 3.0
2012-11-27T11:27:06.713Z
2012-11-27T11:27:06.713Z
SamiD
<p>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 <em>base extension</em>.  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:</p>

<p>$$N = (n_0, n_1, \dots, n_m)$$</p>

<p>where </p>

<p>$$n_0 \equiv N \bmod p_0$$
$$n_1 \equiv N \bmod p_1$$
$$\dots$$</p>

<p>$$n_m \equiv N \bmod p_m$$</p>

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

<p><strong>How quickly can we get the <em>new</em> 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?</strong></p>

<ds.algorithms><upper-bounds>
How quickly can we perform base extension in a residue number system?
Matt Groff
# How quickly can we perform base extension in a residue number system?

(Asked by: username_0 on 2012-11-19)

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?**

**Tags:** ds.algorithms, upper-bounds

---

## 1 answers

### Answer by username_1 on 2012-11-27. Score: 4

Check out Lemma 4.4 in [HesseAllenderBarrington](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.8928) - 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).


---

