Specific modular multiplication algorithm [duplica

问题:

This question already has answers here:

Calculate a*a mod n without overflow (5 answers)

Closed 6 years ago.

I have 3 large 64 bit numbers: A, B and C. I want to compute:

(A x B) mod C

considering my registers are 64 bits, i.e. writing a * b actually yields (A x B) mod 2⁶⁴.

What is the best way to do it? I am coding in C, but don't think the language is relevant in this case.

---

After getting upvotes on the comment pointing to this solution:

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

let me be specific: this isn't a solution, because ((a % c) * (b % c)) may still be bigger than 2⁶⁴, and the register would still overflow and give me the wrong answer. I would have:

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

回答1:

As I have pointed in comment, Karatsuba's algorithm might help. But there's still a problem, which requires a separate solution.

Assume

A = (A1 << 32) + A2

B = (B1 << 32) + B2.

When we multiply those we get:

A * B = ((A1 * B1) << 64) + ((A1 * B2 + A2 * B1) << 32) + A2 * B2.

So we have 3 numbers we want to sum and one of this is definitely larger than 2^64 and another could be.

But it could be solved!

Instead of shifting by 64 bits once we can split it into smaller shifts and do modulo operation each time we shift. The result will be the same.

This will still be a problem if C itself is larger than 2^63, but I think it could be solved even in that case.