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