0

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

user650521
  • 583
  • 1
  • 9
  • 23

3 Answers3

10

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

and

((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).

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
  • 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 02 '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 02 '12 at 10:18
  • Both the numbers are same..That was a typo int question – user650521 Sep 02 '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 02 '12 at 10:41
  • 1
    (A*B)%C = (A%C * B&C)%C Prime-factor each term in the product 67527574 can be prime factored to: (2)(41)(137)(6011) 78627765 can be primed factored to : (3)(5)(2003)(2617) Therefore, (67527574)(78627765) is: (2)(41)(137)(6011)(3)(5)(2003)(2617) or ordered, (2)(3)(5)(41)(137)(2003)(2617)(6011) Now apply the modulus chaining technique I described earlier, and you'll have your answer. Hint: start with the large numbers and work down. – WhozCraig Sep 02 '12 at 15:10
1

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?

Eric Postpischil
  • 195,579
  • 13
  • 168
  • 312
1

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 r = (uint64)a * (uint64)b;
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