How quickly can we decompose a number into a set of residues? Basically, if we are given a natural $x$, in binary, with $x &lt; m_0 \cdot m_1 \cdot m_2 \cdot \dots \cdot m_n$, how quickly can we find $x \bmod m_0$, $x \bmod m_1$,..., and $x \bmod m_n$?  In other words, how quickly can we find $n$ residues in modular arithmetic?  Note that the residues needn't be primes.

I suppose that this is a fairly broad question, and I'm curious if there are special cases where we can find these residues much faster (in other words, if there are special values for the modulus that allow faster calculations).  My motivation is that I'm entertaining some ideas concerning integer multiplication.  Along these lines, I'd like to break apart numbers into smaller residues.  I'm interested in any results besides the trivial situation when some of the moduli are powers of 2.
If $m=2^k-t$ where $t$ is small, then you can reduce modulo $m$ faster.  In particular, $a \cdot 2^k + b \equiv at+b \pmod{m}$, so reducing an $\alpha k$-bit number modulo $m$ typically requires $\alpha$ multiplications by $t$ and $\alpha$ additions.  This can be significantly faster than the normal algorithms, if $t$ is small enough.

Something similar holds for $m=2^k+t$, too.

So, one plausible approach is to choose a modulus $m$ that is a product $m=m_1 m_2 \cdots m_n$ where each $m_i$ has the form $2^k \pm t$, where $k$ is the word size of your computer (e.g., $k=64$).