Why is pow(a, d, n) so much faster than a**d % n?

我当时正在尝试实现一个 Miller-Rabin primality test，我很困惑为什么对于中等大小的数字(大约7位数字)要花这么长的时间(> 20秒)。我最终发现下面这行代码是问题的根源:

x = a**d % n

(where a, d, and n are all similar, but unequal, midsize numbers, ** is the exponentiation operator, and % is the modulo operator)

然后我试着用下面的代替它:

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

还有一个相关的问题，为什么当使用 Python2或3运行时，这个计算的速度几乎是 PyPy 的两倍，而 PyPy 通常是 快多了？