Take the 2-minute tour ×

As we know 1000000007 is a large prime number. How can I find multiplication of two large numbers modulo 1000000007

For example if I want to find 78627765*67527574 mod 1000000007, how can I do it.

At least if anyone tell me the procedure I shall try

Note: pls let me know the solution with primitive datatypes like int,long or long long Thanks in advance

share|improve this question
Take the numbers in strings and multiply them, storing result in another string. OR you can take long long int. –  Coding Mash Sep 2 '12 at 10:00
I wish to use only primitive data type, any other method? –  user650521 Sep 2 '12 at 10:14
Does this fit: stackoverflow.com/questions/565150/bigint-in-c ? –  dualed Sep 2 '12 at 10:17
for primitive types see craigs answer below –  dualed Sep 2 '12 at 10:21
Looks like you are trying you hand at problems from Codechef? –  Cupidvogel Sep 2 '12 at 10:23

3 Answers 3

Modulo chaining works with reasonable numbers that are pushing the limits of your numerical comp-space:

(A * B) % C == ((A % C) * (B % C)) % C.

The proof for this is pretty straight forward and there are literally thousands of examples on cryptography websites all over the world. A simple sample:

(7 * 8) % 5 = 56 % 5 = 1


((7 % 5) * (8 % 5)) % 5 = (2 * 3) % 5 = 6 % 5 = 1

I hope this helps. Obviously when A and B are already pushed to your top-end platform limits and are still smaller than C, it gets pointless, but it can be very handy when this is not the case (I.e. when A > C and/or B > C).

share|improve this answer
In my case if you multiply both the values , it exceeds the capacity of primitive datatype and my intention is to use this only using primitive datatypes like int, long or long long. –  user650521 Sep 2 '12 at 10:12
I probably should have accounted for both modulus you had in your question. In one case, you have 100000007, and on the next line, 10000007. That extra order of magnitude is what will break chaining in this case. If you meant the latter and not the former, chaining will solve this for with no fancy tricks or bigint libs. It will NOT help if you meant the former and not the latter. I apologize if thats the case. –  WhozCraig Sep 2 '12 at 10:18
Both the numbers are same..That was a typo int question –  user650521 Sep 2 '12 at 10:20
Fair enough. Sorry about that. That being the case, if you were looking for a general solution a big int lib is likely your best bet. If you're looking at this specific problem you may try pre-factoring your multiplicative terms first and rearranging the factors to push one of the terms beyond your mod base (and therefore chain), (but not too far =). I have a feeling that you're more interested in a general code-solution though. (it is, after all, why we're all here, isn't it?) –  WhozCraig Sep 2 '12 at 10:41
I dont want code solution.. Theory would suffice –  user650521 Sep 2 '12 at 10:49

Since this looks like a homework or context problem, I will only give hints.

If you know x%m and y%m, how can you find (x+y)%m? If you know x%m, how can you find (2x)%m?

Since you want to find (a*b)%m, is there a way you can decompose b so that you can use the above two hints?

share|improve this answer

Why don't you want to use 64-bit arithmetic for that ? Of course this only works if the operands being multplied do not exceed 32 bits each (but this can also be fixed). Consider:

typedef unsigned long long uint64;
uint64 m = 1000000007UL;
uint64 r = (uint64)a * (uint64)b;
r = r % m; // get the residue

One can also optimize it to avoid '%' which might be expensive:

double inv = 1.0 / 1000000007UL; // precompute inverse
uint64 rf = (uint64)floor((double)a * (double)b * inv); // floor(a * b / m) 
r = r - rf * m; //  residue

Note that the second method may require some playing around with accuracy. You can also use 'long double' instead

share|improve this answer

Your Answer


