modular multiplication of large numbers in c++

algorithm, c++, modular, multiplication

Solution

Given your formula and a the following variation:

(A + B) mod C = ((A mod C) + (B mod C)) mod C

You can use the divide and conquer approach to develope an algorithm that is both easy and fast:

#include <iostream>

long bigMod(long  a, long  b, long c) {
    if (a == 0 || b == 0) {
        return 0;
    }
    if (a == 1) {
        return b;
    }
    if (b == 1) {
        return a;
    } 

    // Returns: (a * b/2) mod c
    long a2 = bigMod(a, b / 2, c);

    // Even factor
    if ((b & 1) == 0) {
        // [((a * b/2) mod c) + ((a * b/2) mod c)] mod c
        return (a2 + a2) % c;
    } else {
        // Odd exponent
        // [(a mod c) + ((a * b/2) mod c) + ((a * b/2) mod c)] mod c
        return ((a % c) + (a2 + a2)) % c;
    }
}

int main() { 
    // Use the min(a, b) as the second parameter
    // This prints: 27
    std::cout << bigMod(64545, 58971, 144) << std::endl;
    return 0;
}

Which is `O(log N)`

Problem

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.

Original source