5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Matt Groff Oct 4 '15 at 3:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.