c - 大きな数のモジュラー乗算

Question

3つの数値のモジュラー乗算を行うための効率的なアルゴリズムを見つける必要があります。

言い換えれば、Cでこれを見つける方法はありますか？

(100100101010001001 * 1010000100100010 * 10010001001010100101001) % 1000000007

Answer 1

整数のオーバーフローを回避したい場合は、変換できます

(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は、結果をオペランドの1つと同じ変数に直接設定することをサポートしていますが、よくわかりません。ドキュメントでこれを確認する必要があります。