modular multiplication of large numbers in c++

Question

I have three integers A, B (less than 10^12) and C (less than 10^15). I want to calculate (A * B) % C. I know that

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

but say if A = B = 10^11 then above expression will cause an integer overflow. Is there any simple solution for above case or I have to use fast multiplication algorithms.

If I have to use fast multiplication algorithm then which algorithm I should use.

EDIT: I have tried above problem in C++ (which does not cause overflow, not sure why), but isn't the answer should be zero?

Thanks in advance.

Answer 1

You can solve this using Schrage's method. This allows you to multiply two signed numbers a and z both with a certain modulus m without generating an intermediate number greater than that.

It's based on an approximate factorisation of the modulus m,

m = aq + r 

i.e.

q = [m / a]

and

r = m mod a

where [] denotes the integer part. If r < q and 0 < z < m − 1, then both a(z mod q) and r[z / q] lie in the range 0,...,m − 1 and

az mod m = a(z mod q) − r[z / q]

If this is negative then add m.

[This technique is frequently used in linear congruential random number generators].