Tag: 模运算

特定的模乘算法

我有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.