5
$\begingroup$

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.

$\endgroup$
2
  • 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
2
$\begingroup$

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?

$\endgroup$
4
  • $\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
4
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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 !

$\endgroup$

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.