Simplify [(a*b) mod n] mod m 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.
 A: 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.
A: 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.
A: 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 $$
