[解決済み] なぜ pow(a, d, n) は a**d % n よりも速いのですか？

質問

を実装しようとしていたのですが ミラー・ラビン一次性検定 を実装しようとしていたのですが、中程度の数 (~7 digits) でなぜこんなに時間がかかるのか (> 20 seconds) 困惑していました。最終的に、次のコードの行が問題の原因であることを発見しました。

x = a**d % n

(ここで a , d そして n はいずれも似て非なる中型の数字である。 ** は指数演算子、そして % はモジュロ演算子)

次に私は、以下のように置き換えてみました。

x = pow(a, d, n)

であり、それに比べればほとんど瞬時である。

文脈上、元の関数は以下の通りです。

from random import randint

def primalityTest(n, k):
    if n < 2:
        return False
    if n % 2 == 0:
        return False
    s = 0
    d = n - 1
    while d % 2 == 0:
        s += 1
        d >>= 1
    for i in range(k):
        rand = randint(2, n - 2)
        x = rand**d % n         # offending line
        if x == 1 or x == n - 1:
            continue
        for r in range(s):
            toReturn = True
            x = pow(x, 2, n)
            if x == 1:
                return False
            if x == n - 1:
                toReturn = False
                break
        if toReturn:
            return False
    return True

print(primalityTest(2700643,1))

時限計算の例です。

from timeit import timeit

a = 2505626
d = 1520321
n = 2700643

def testA():
    print(a**d % n)

def testB():
    print(pow(a, d, n))

print("time: %(time)fs" % {"time":timeit("testA()", setup="from __main__ import testA", number=1)})
print("time: %(time)fs" % {"time":timeit("testB()", setup="from __main__ import testB", number=1)})

出力（PyPy 1.9.0での実行）。

2642565
time: 23.785543s
2642565
time: 0.000030s

出力 (Python 3.3.0 で実行、2.7.2 は非常に似た時間を返します)。

2642565
time: 14.426975s
2642565
time: 0.000021s

そして関連する質問ですが、なぜこの計算をPython 2や3で実行すると、PyPyで実行するよりも2倍近く速くなるのか、通常PyPyでは より速い ?

どのように解決するのですか？

Wikipedia の モジュール式指数関数 . 基本的には a**d % n を計算する必要があります。 a**d を計算しなければならず、これはかなり大きくなる可能性がある。 しかし a**d % n を計算することなく a**d を計算することなく、その分 pow が行うものです。 その ** 演算子は、すぐにモジュラスを取ろうとしていることを知るために、未来を見通すことができないので、これを行うことはできません。