具体的模乘算法 [英] Specific modular multiplication algorithm
问题描述
我有3个大的64位数字：A，B和C我想计算：
（A×b）个模ç
考虑我的寄存器都是64位的，即编写 A * B 实际产量（A X B）模2⁶⁴。
什么是做到这一点的最好方法是什么？我编码在C，但不认为语言是相关的在这种情况下。
获得的评论upvotes指向该解决方案后：
（A * B）％C ==（（A％C）*（B％C））％C
让我具体的：这不是一个解决方案，因为（（A％C）*（B％C））仍可能大于2⁶⁴，寄存器仍然会溢出，给我错误的答案。我想有：
（（（A MODÇ）×（B MOD C））模2⁶⁴）MODç
正如我已经指出的评论，Karatsuba的算法可能有帮助。但还是有一个问题，它需要单独的解决方案。
假设
A =（A1中;＆LT; 32）+ A2
B =（B1，其中;＆所述; 32）+ B2
当我们乘那些我们得到：
A * B =（（A1 * B1）＆LT;＆LT; 64）+（（A1 * B2 + A2 * B1）＆LT;＆LT; 32）+ A2 * B2
所以，我们有3个数字，我们要总结和这一次肯定是大于2 ^ 64，另一个可能是。
但也有可能得到解决！
而不是64位的移位，一旦我们可以把它分割成更小的变化，做模运算每次我们转移时间。结果将是相同的。
这仍然是一个问题，如果C本身是大于2 ^ 63大，但我认为它甚至可以在这种情况下得到解决。
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
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.
这篇关于具体的模乘算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
