c++ - unsigned long long AおよびBに対してオーバーフローなしで（A * B）mod Mを実行する方法はありますか？

Question

WindowsにGMPをインストールするという悪夢は望んでいません。

私は2つの数AとB、unsigned long longsを持っており、最大で10 ^ 10程度の大きさですが、それを行っても((A%M)*(B%M))%M整数のオーバーフローが発生します。

(A*B)%Mより大きな数を計算するための自作関数はありますか？

Answer 1

モジュラスMがよりも十分に小さい場合ULLONG_MAX（10 ^ 10の領域にある場合）、係数の1つを2つの部分に分割することにより、3つのステップでそれを行うことができます。私はそれと、、A < Mとを仮定します。B < MM < 2^42

// split A into to parts
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1);
unsigned long long temp = (a1 * B) % M;   // doesn't overflow under the assumptions
temp = (temp << 21) % M;                  // this neither
temp += (a2*B) % M;                       // nor this
return temp % M;

値が大きい場合は、係数を3つの部分に分割できますが、モジュラスが実際にULLONG_MAXそれに近づくと、醜くなります。