Esta pergunta já tem uma resposta aqui:

Tenho 3 números grandes de 64 bits: A, B e C. Quero calcular:

(A x B) mod C

considerando que meus registros são de 64 bits, ou seja, escrevendoa * b realmente produz (A x B) mod 2⁶⁴.

Qual é a melhor maneira de fazer isso? Estou codificando em C, mas não acho que o idioma seja relevante neste caso.

Depois de receber votos no comentário apontando para esta solução:

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

eixe-me ser específico: esta não é uma solução, porque ((a% c) * (b% c)) ainda pode ser maior que 2⁶⁴, e o registro ainda excederá e me fornecerá a resposta errada. Eu teria

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