优化乘法模数小素数

Question

我需要做下面的操作很多次:

我的直觉是天真

result = a * b
result %= p

效率低下.我可以优化乘法模数p,就像求幂模p优化一样pow(a, b, p)吗？

Answer 1

你提到" a, b与p具有相同的数量级". 通常在密码学中,这意味着a,b接近大数p,但严格小于p.

如果是这种情况,那么您可以使用简单身份

$ap\equiv a\pmod {p}$

把你的计算变成

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

然后你将一个大的乘法变成了两个大的减法和一个小的乘法.您将需要进行分析以查看哪个更快.

如果你可以将所有结果保存在机器本机整数中,而不是要求升级到Python的任意精度整数(当值大到足以要求它们时无缝地发生),你可以节省大量时间.这看起来是一种很好的方法.(当然,正如答案所说,你应该进行自己的测试,看看它实际上是否*更快.) (2认同)
只要 a、b 和 p 都是 32 位整数（如在 OP 中），我认为这不会有帮助。 (2认同)

Answer 2

要在汇编中进行此计算,但是可以从Python调用它,我将尝试使用C编写的 Python模块进行内联汇编.无论GCC和 MSVC 编译器功能内联汇编,只能用不同的语法.

请注意,我们的模数p = 1000000007恰好适合30位.所需的结果(a*b)%p可以在英特尔80x86寄存器中计算,因为一些a,b不太大的限制p.

对规模的限制 a,b

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

(2)a*b小于p << 32,即p2 ^ 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节.我们想要的结果就是余数.

如果分子EDX:EAX中的64位乘积由于未满足上述(2)而给出大于32位的商,则该除法指令DIV存在溢出的风险.

我正在使用C/inline程序集中的代码片段来进行"概念验证".但是,速度的最大好处将取决于a,b在Python中批处理数据数组,分摊函数调用的开销等(如果这是目标平台).