优化小素数的取模乘法

Question

我需要做以下操作很多次：

1. 取两个整数 a, b
2. 计算 a * b mod p，其中 p = 1000000007，并且 a, b 的大小和 p 差不多

我感觉简单的做法

result = a * b
result %= p

效率不高。我能像优化指数运算那样，优化模 p 的乘法吗？比如用 pow(a, b, p) 这种方式？

Answer 1

这段话虽然没有直接回答问题，但我建议如果你想要提高性能，就不要仅仅用纯Python来做。这里有几个选择：

• 可以用C语言做一个小库来处理你的计算，然后用Python的 ctypes 来和它沟通。
• 使用 numpy；如果你不想自己编译东西，这可能是最好的选择。一次只做一个操作的速度不会比Python自带的操作快，但如果你把多个操作放在一个numpy数组里，进行计算的速度会比在Python里快很多。
• 使用 cython 来把你的变量声明为C整数；同样的道理，如果你批量处理，会更有利于提高效率（因为那样你也可以优化循环）。

Answer 2

你提到“a, b 和 p 的数量级是相同的。”在密码学中，这通常意味着 a 和 b 是接近 p 的大数字，但严格来说要小于 p。

如果是这样的话，你可以使用一个简单的公式：

这样你就可以把计算变成：

result = ((a-p)*(b-p))%p

这样一来，你就把一个大的乘法变成了两个大的减法和一个小的乘法。你需要测试一下，看看哪种方式更快。

Answer 3

要在汇编语言中进行这个计算，并且能从Python调用，我会尝试在用C写的Python模块中使用内联汇编。GCC和MSVC编译器都支持内联汇编，只是语法有所不同。

注意我们的模数 p = 1000000007 刚好适合30位。我们想要的结果 (a*b)%p 可以在Intel 80x86寄存器中计算，只要 a,b 不比 p 大太多。

关于 a,b 大小的限制

(1) a,b 是32位无符号整数

(2) a*b 小于 p << 32，也就是 p 乘以2的32次方

特别地，如果 a,b 都小于 2*p，就能避免溢出。根据(1)，只要其中一个小于 p 也可以。

Intel 80x86指令MUL可以将两个32位无符号整数相乘，并将64位的结果存储在累加器寄存器对EDX:EAX中。关于MUL的一些细节和特点可以在这个有用的总结的第10.2.1节中找到。

接着，指令DIV可以将这个64位的结果除以一个32位的常数（模数 p），将商存储在EAX中，将余数存储在EDX中。有关更多信息，请参见上一个链接的第10.2.2节。我们想要的结果就是这个余数。

需要注意的是，这个除法指令DIV可能会导致溢出，如果64位的分子EDX:EAX的商大于32位，而没有满足上面的(2)条件。

我正在用C/内联汇编编写一个代码片段，作为“概念验证”。不过，速度的最大提升将取决于将数据数组 a,b 批量处理，以分摊在Python中调用函数的开销等（如果这是目标平台的话）。