<p>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.</p>

<p>Something similar holds for $m=2^k+t$, too.</p>

<p>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$).</p>

CC BY-SA 3.0
2015-10-04T03:43:13.610Z
I had actually considered this already.  I considered finding values modulo products of these $m$'s, and successively breaking apart the products into smaller pieces.  The idea was to reduce the amount of multiplications.  Along slightly different lines, I figured that since the multiplications could possibly be repetitive, it may be worthwhile to look into multiplication by a constant - the constant being any intermediate value that is used multiple times.  Unfortunately, none of these ideas seemed to really help much with efficiency.
Matt Groff
CC BY-SA 3.0
2015-10-04T03:05:03.140Z
2015-10-04T03:05:03.140Z
D.W.
<p>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?  <em>Note that the residues needn't be primes.</em></p>

<p>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.</p>

<arithmetic-circuits>
How quickly can we decompose a number into a set of residues?
Matt Groff
# How quickly can we decompose a number into a set of residues?

(Asked by: username_0 on 2015-10-03)

Basically, if we are given a natural $x$, in binary, with $x < 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.

**Tags:** arithmetic-circuits


---

## 1 answers

### Answer by username_1 on 2015-10-04. Score: 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$).

> **Comments:**
> **username_0**: I had actually considered this already.  I considered finding values modulo products of these $m$'s, and successively breaking apart the products into smaller pieces.  The idea was to reduce the amount of multiplications.  Along slightly different lines, I figured that since the multiplications could possibly be repetitive, it may be worthwhile to look into multiplication by a constant - the constant being any intermediate value that is used multiple times.  Unfortunately, none of these ideas seemed to really help much with efficiency.  

---

