Find modulo of multiplication of two number?

Question

Given $m$, $a$ and $b$ are very big numbers, how do you calculate $ (a*b)\pmod m$ ?

As they are very big number I can not calculate $(a*b)$ directly. So I need another method.

Answer 1

As far as I know, there are no general shortcuts besides reducing the terms of the product before multiplying. I will emphasize that by reduction, I mean picking the smallest representative mod $m$ in absolute value. This may be a negative integer.

Having said that, there are tricks that can be used in special cases. The most basic integer arithmetic on a computer is not actually integer arithmetic, but rather, modulo $2^n$ for some $n$ (usually 32 or 64). Since the integers are represented in binary, bits do not need to be computed in the product after the $n+1$^st bit has been computed, because those higher bits only contribute 0's. In general, if your integers are represented in base $e$, and $m$ divides $e^k$, then you don't have to compute the digits of the product above the $k+1$ term.

Another trick is to factor $m$ and use the Chinese Remainder Theorem to work with smaller numbers.

I'm sure there are many other tricks I've missed as well. If you're looking for a general algorithm, though, you won't find one that avoids arduous multiplication in all cases. Besides, multiplication is actually easy for a computer to do. Are you trying to do this by hand, or are the numbers really too big for a computer to handle?

Answer 2

If $a,b,m$ are integers then you can use following property :

$a \equiv a_1 \pmod m \land b \equiv b_1 \pmod m \Rightarrow a\cdot b \equiv a_1 \cdot b_1 \pmod m$