Diese Frage hat hier bereits eine Antwort:

Ich habe 3 große 64-Bit-Zahlen: A, B und C. Ich möchte berechnen:

(A x B) mod C

enn ich meine Register als 64 Bit betrachte, d. h. wenn ich @ schreia * b ergibt tatsächlich (A x B) mod 2⁶⁴.

Was ist der beste Weg, um es zu tun? Ich programmiere in C, glaube aber nicht, dass die Sprache in diesem Fall relevant ist.

Nachdem der Kommentar, der auf diese Lösung verweist, positiv bewertet wurde:

(a * b) % c == ((a % c) * (b % c)) % c

Lassen Sie mich genau wissen: Dies ist keine Lösung, da ((a% c) * (b% c)) möglicherweise immer noch größer als 2⁶⁴ ist und das Register immer noch überläuft und mir die falsche Antwort gibt. Ich hätte

(((A mod C) x (B mod C)) mod 2⁶⁴) mod C