python - 如何提高 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 内存 8GB，运行 Ubuntu 12.04 32bit 机器。

使用像 gmpy2 这样的库来提升它是否有意义，或者没有任何优势？

Answer 1

您似乎是先计算所有数字的乘积，然后取余数，而不是利用模乘法的特性:a * b * c mod p == (a * b mod p) * c修改 p。将 10,000 个 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

对于你，我建议:

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