如何提高 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。将 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

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

How to boost efficiency for large number modulus multiplications in Python

python

python-3.x

gmpy