c++ - how to find muliplication of large numbers modulo 100000007

Question

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

Answer 1

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