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.
$\begingroup$
$\endgroup$
2
asked Jan 14 '12 at 15:27
-
1$\begingroup$ If $a$ and $b$ are not already reduced mod $m$, reducing them first helps. Ultimately, though, I think you have to at least partially compute the product of the two numbers. $\endgroup$ – Dustan Levenstein Jan 14 '12 at 15:31
-
$\begingroup$ I'll do that for sure. But I want to know how to achieve it after computing $\pmod m$ $\endgroup$ – Shiplu Mokaddim Jan 14 '12 at 16:18
Add a comment
|
$\begingroup$
$\endgroup$
4
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?
answered Jan 14 '12 at 16:35
-
$\begingroup$ Since you used the $a \mod m$ notation, it occurs to me that you might not already know about modular arithmetic, which is slightly different: en.wikipedia.org/wiki/Modular_arithmetic. $\endgroup$ – Dustan Levenstein Jan 14 '12 at 16:47
-
$\begingroup$ The number is too big. It should overflow computers integer boundary by definition. $\endgroup$ – Shiplu Mokaddim Jan 14 '12 at 16:58
-
$\begingroup$ Do you mean that the product is larger than your computer's maxint? There are tools for multiplying numbers larger than the so-called maxint. $\endgroup$ – Dustan Levenstein Jan 14 '12 at 17:02
-
$\begingroup$ If that's the case, then this is a computer science question rather than a math question. $\endgroup$ – Dustan Levenstein Jan 14 '12 at 17:05
$\begingroup$
$\endgroup$
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$
answered Jan 14 '12 at 15:44
$\begingroup$
$\endgroup$
You can exploit the binary representation of these two numbers. Suppose we have to multiply (a*b)%c where 0<=a,b,c<=10^18. Then we can use this method:
ull mulmod(ull a,ull b,ull c){
if(a<=1000000000ULL && b<=1000000000ULL){
ull ret = ((a%c)*(b%c))%c;
return ret;
}
ull ret = 0ULL, a=a%c;
while(b > 0ULL){
if(b&1ULL) {
ret = (ret+a)%c;
}
a = (a<<1ULL)%c;
b>>=1ULL;
}
return ret%c;
}
Hope this helps !
