На этот вопрос уже есть ответ:

У меня есть 3 больших 64-битных числа: A, B и C. Я хочу вычислить:

(A x B) mod C

учитывая, что мои регистры 64-битные, т.е. пишуa * b на самом деле дает (A x B) мод 2⁶⁴.

Какой лучший способ сделать это? Я пишу на C, но не думаю, что в данном случае язык уместен.

После получения комментариев по поводу этого решения:

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

Позвольте мне быть конкретным: это не решение, потому что ((a% c) * (b% c)) может быть больше 2⁶⁴, и регистр все равно переполнится и даст мне неправильный ответ. Я бы

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