5

I know that instead of computing (a*b) mod n, I can also compute more efficiently on smaller numbers via [(a mod n)*(b mod n)] mod n.

(I need the last mod n, because my result needs to be smaller than n)

Is there a way I can easily compute [(a*b) mod n] mod m, for $m<n$?

Unfortunately, [(a mod n mod m)*(b mod n mod m)] mod m does not give the same results.

torpedo
  • 121

3 Answers3

2

This isn't well-defined unless $m$ divides $n$. To see why, consider $m=3$, $n=4$, $a=b=1$. Then you're looking to reduce $(1\pmod{4})\pmod{3}$. $1\pmod{3}$ is the set of integers which give that remainder upon division by 4: $\{\dots,-3,1,5,9,\dots\}$, and taking each of those modulo 3, we find $\{\dots,0,1,2,0,\dots\}$, that is, you don't always get the same value!

Trying instead $m=2$, we see that taking modulo 2 finds $\{\dots,1,1,1,1,\dots\}$. And, more generally, if $n=km$, then $ab\pmod{n}$ is simply the task of writing $ab=xn+r$ where $0\le r<n$, but this rewrites as $ab=xkm+(ym+s)=(xk+y)m+s$ where $0\le s<m$, so $s$ is the remainder modulo $m$ and this reduction makes sense.

In this second case, taking modulo $n$ and then modulo $m$ is a little redundant so you might as well just take modulo $m$ throughout.

zjs
  • 1,125
  • 5
  • 9
0

Let’s assume $a$ and $b$ are positive and we just want the smallest positive value when taking mod’s. Otherwise the problem isn’t well defined.

One way to calculate $a*b \mod n$ is through recursion. If $a$ is even, calculate $(a/2)*b \mod n$, then double the answer and maybe subtract $n$. Similarly, if $a=2x+1$, then $ab=2xb+b$. By repeatedly breaking multiplication into smaller sub problems, you can calculate the sum in at most $3log_2(a)$ additions and subtractions while only dealing with numbers of size smaller than $2n$. You could then apply $\mod m$ to the result. This approach is particularly useful in computer science when you want to avoid integer overflow.

Eric
  • 6,348
0

As already stated in another answer, if $n$ is divisible by $m$ then :

$$ [(a \cdot b) \bmod n] \bmod m = \\ (a \cdot b) \bmod m = \\ [ (a \bmod m) \cdot (b \bmod m) ] \bmod m $$

The efficiency here can be increased like this: (to subtract the large values first and then the small ones, on average decreasing the number of total subtractions to calculate ($x \bmod m$)):

$$ [ ((a \bmod n) \bmod m) \cdot ((b \bmod n) \bmod m) ] \bmod m $$

But in general, (if $n$ is not necessarily divided by $m$) using your own formula we get:

$$ [(a \cdot b) \bmod n] \bmod m = \\ ([ (a \bmod n) \cdot (b \bmod n) ] \bmod n) \bmod m $$

Vladimir Fokow
  • 352