Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Dustan Levenstein Jan 14 '12 at 15:31
    
I'll do that for sure. But I want to know how to achieve it after computing $\pmod m$ –  Shiplu Jan 14 '12 at 16:18
add comment

3 Answers

up vote 1 down vote accepted

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?

share|improve this answer
    
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. –  Dustan Levenstein Jan 14 '12 at 16:47
    
The number is too big. It should overflow computers integer boundary by definition. –  Shiplu Jan 14 '12 at 16:58
    
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. –  Dustan Levenstein Jan 14 '12 at 17:02
    
If that's the case, then this is a computer science question rather than a math question. –  Dustan Levenstein Jan 14 '12 at 17:05
add comment

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$

share|improve this answer
add comment

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 !

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.