Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
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|cite|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: – 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

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|cite|improve this answer

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;
    return ret%c;

Hope this helps !

share|cite|improve this answer

Your Answer


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.