To pytanie ma już odpowiedź tutaj:

Mam 3 duże 64-bitowe liczby: A, B i C. Chcę obliczyć:

(A x B) mod C

rozważenie moich rejestrów to 64 bity, tj. zapisa * b faktycznie daje (A x B) mod 2⁶⁴.

Jak najlepiej to zrobić? Piszę w języku C, ale nie sądzę, że język jest odpowiedni w tym przypadku.

Po otrzymaniu pozytywnych opinii na temat komentarza do tego rozwiązania:

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

pozwól mi być konkretnym: to nie jest rozwiązanie, ponieważ ((a% c) * (b% c)) może nadal być większe niż 2⁶⁴, a rejestr nadal przepełnia się i daje mi złą odpowiedź. Miałbym

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