Let a, b, and c be long long (int64) numbers, how to calculate (a*b)%c? The problem here is that you can't multiply (a%c)*(b%c) because it won't fit on an int64 variable. So, what can it be done?
Just in case it's helpful, I'm jusing C++.
How to calculate the result of the multiplication of two int64 numbers modulus another int64 number?
Asked
Active
Viewed 625 times
0
-
FWIW, `%` is the remainder operator _not_ modulus. Do you really need modulus or is `(a*b) >= 0 && c > 0` always true? – ldav1s May 08 '13 at 03:12
-
possible duplicate of [overflow possibilities in modular exponentiation by squaring](http://stackoverflow.com/questions/16426557/overflow-possibilities-in-modular-exponentiation-by-squaring) – Daniel Fischer May 08 '13 at 11:42
-
The question in the suggested duplicate doesn't look identical immediately, but it's the same problem, modular multiplication for large moduli. – Daniel Fischer May 08 '13 at 11:43
1 Answers
0
You could use an arbitrary precision library such as gmp to ensure that you'll never overflow your numerical type.
or you ensure that your multiplication will not overflow your type. Without knowing more about your input, I can't really speculate on good ways to do that.
Or this question is very applicable to your task.
