符号なしlong long AとBに対してオーバーフローのない（A * B）mod Mを行う方法はありますか？

Question

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

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

数字が大きい場合は(A*B)%Mを計算するための自作関数がありますか？

Answer 1

モジュラスMがULLONG_MAX（これが10^10の領域にある場合）よりも十分に小さい場合は、2つの要素の1つを分割することで3段階で行うことができます。私はそれがA < MとB < MとM < 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に本当に近くなった場合、それは醜いとなります。