Modular multiplication of large numbers

Question

I need to find an efficient algorithm for doing modular multiplication of three numbers.

In other words is there a way to find this in C?

(100100101010001001 * 1010000100100010 * 10010001001010100101001) % 1000000007

Answer 1

If you are looking to avoid integer overflow, you can transform

(a * b * c) % d

into

((((a % d) * (b % d)) % d) * (c % d)) % d

In C:

unsigned long work(unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
    unsigned long r = a % d;
    r *= b % d;
    r %= d;
    r *= c % d;
    r %= d;
    return r;
}

It can still overflow though, but less often than the naïve version. If you want to be positively sure it will not overflow then you should use some form of big numbers library like gmplib. The usage would look like:

unsigned long work(unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
    mpz_t tmp, res;
    unsigned long r;
    mpz_init_set_ui(tmp, a);
    mpz_mul_ui(res, tmp, b);
    mpz_mul_ui(tmp, res, c);
    mpz_mod_ui(res, tmp, d);
    r = mpz_get_ui(res);
    mpz_clear(res);
    mpz_clear(tmp);
    return r;
}

Maybe Gmplib supports directly setting the result into the same variable as one of the operand but I am not sure. You would have to check this in the documentation.