我有 3 个大的 64 位数字：A、B 和 C。我想计算：
(A x B) mod C
考虑到我的寄存器是 64 位，即写入a * b实际上产生 (A x B) mod 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
正如我在评论中指出的那样，Karatsuba 的算法可能会有所帮助。但是仍然存在一个问题，需要单独的解决方案。
认为
A = (A1 << 32) + A2
B = (B1 << 32) + B2。
当我们将这些相乘时，我们得到：
A * B = ((A1 * B1) << 64) + ((A1 * B2 + A2 * B1) << 32) + A2 * B2。
所以我们有 3 个要求和的数字，其中一个肯定大于 2^64，另一个可能更大。
但是可以解决！
我们可以将其拆分为更小的移位并在每次移位时进行模运算，而不是移位 64 位。结果将是相同的。
如果 C 本身大于 2^63，这仍然是一个问题，但我认为即使在这种情况下也可以解决。