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

Question

我正在使用没有任何定制库的python3来进行一些简单的算术运算。支配计算效率的运算是许多 2048 位值的乘法：

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

为了让您深入了解，将 10000 次乘法模数制作为一个数字需要约 3940 秒：

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. 将 10,000 个 2048 位数字以 some 为模乘以很少的时间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

对于你，我建议：

array = map(int, array)
prod = 1
for x in array:
    prod *= x
    prod %= n2