为什么pow（a，d，n）比a ** d％n快得多？

Question

我试图实施Miller-
Rabin素数测试
，并且对为什么中型数字（〜7位数字）花费如此长时间（>
20秒）感到困惑。我最终发现以下代码行是问题的根源：

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时快一倍，而通常PyPy要快得多？

Answer 1

请参阅Wikipedia上有关模幂的文章。基本上，当您这样做时a**d % n，实际上必须计算a**d，这可能会很大。但是有很多计算方法，a**d % n而不必自己计算a**d，这就是pow它的作用。该**运营商不能做到这一点，因为它不能“预见未来”知道你要立即采取模数。