I have 3 large 64-bit numbers: A, B and C. I want to calculate:
(A x B) mod C
given that my registers are 64 bits, i.e. the entry a * bactually gives (A x B) mod 2⁶⁴.
What is the best way to do this? I code in C, but I don’t think that in this case the language matters.
After receiving comments in the comments pointing to this decision:
(a * b) % c == ((a % c) * (b % c)) % c
Let me be specific: this is not a solution because ((a% c) * (b% c)) can still be more than 2⁶⁴ and the register will still overflow and give me the wrong answer. I'd:
(((mod mod C) x (B mod C)) mod 2⁶⁴) mod C
source
share