2

簡単な算術演算用に調整されたライブラリなしで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 のようなライブラリを使用してブーストすることは理にかなっていますか、それとも利点はありませんか?

4

1 に答える 1

6

剰余乗算のプロパティを利用するのではなく、最初にすべての数値の積を計算してから剰余を取っているようです: 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
于 2015-02-18T13:32:20.853 に答える