如何提高Python中大数模乘法的效率

Question

我使用的python3没有任何定制的库用于一些简单的算术。控制计算效率的运算是许多2048位值的乘法：

length=len(array)
res=1
for x in range(length):
       res=(res*int(array[x]))
       ret=res%n2

为了让您深入了解，每次乘法需要大约3940秒才能将10000次乘法模为一个数：

Intel Core i5 CPU M 560 @ 2.67GHz × 4 with 8GB of memory, running Ubuntu 12.04 32bit机器。在

使用gmpy2这样的库来提升它是有意义的还是没有任何好处？在

Answer 1

你似乎是先计算所有数的乘积，然后取余数，而不是利用模乘的性质：a * b * c mod p == (a * b mod p) * c mod p。将10000个2048位数字乘以某个n所需的时间非常少：

In [1]: import random

In [2]: array = [random.randrange(2**2048) for i in range(10000)]

In [3]: n = random.randrange(2**2048)

In [4]: prod = 1

In [5]: %%time
   ...: for e in array:
   ...:         prod *= e
   ...:         prod %= n
   ...: 
CPU times: user 210 ms, sys: 4.07 ms, total: 214 ms
Wall time: 206 ms

对你来说，我建议：

^{pr2}$