c - 大数的模乘

我需要找到一个有效的算法来做三个数的模乘。
换句话说，有没有办法在C中找到这个？

(100100101010001001 * 1010000100100010 * 10010001001010100101001) % 1000000007

最佳答案

如果希望避免整数溢出，可以转换

(a * b * c) % d

进入之内

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

在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;
}

但它仍然可以溢出，但比天真的版本要少。如果你想确定它不会溢出，那么你应该使用某种形式的大数字库，比如gmplib。用法如下：

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;
}

也许Gmplib支持直接将结果设置为与某个操作数相同的变量，但我不确定。你必须在文档中检查这个。

关于c - 大数的模乘，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14180999/