c - 大数的模乘法

Question

我需要找到一种有效的算法来进行三个数字的模乘。

换句话说，有没有办法在 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.