特定的模乘算法

我有3个大的64位数字：A，B和C.我想计算：

(A x B) mod C

考虑到我的寄存器是64位，即写a * b实际上产生（A x B）mod2⁶⁴。

最好的方法是什么？我在C编码，但在这种情况下不认为语言是相关的。

在获得指向此解决方案的评论之后：

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

让我具体一点：这不是一个解决方案，因为（（a％c）*（b％c））可能仍然大于2⁶⁴，寄存器仍会溢出并给我错误的答案。我会：

（（（A mod C）x（B mod C））mod2⁶⁴）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，这仍然是一个问题，但我认为即使在这种情况下它也可以解决。