为什么pow（a，d，n）比**d%n快这么多？

我当时正试图实现米勒-拉宾素性测试，但我不明白为什么中等大小的数字（~7位）要花这么长时间（>20秒）。我最终发现以下代码是问题的根源：

x=a**d%n

（其中，a、d和n都是类似但不相等的中型数字，**是求幂运算符，%是模运算符）

然后，我尝试将其替换为以下内容：

x=pow（a、d、n）

相比之下，它几乎是瞬间的

对于上下文，以下是原始函数：

来自随机导入randint的

def初级测试（n，k）：
如果n&lt；2:
返回错误
如果n%2==0：
返回错误
s=0
d=n-1
当d%2==0时：
s+=1
d&gt&gt；=1.
对于范围（k）内的i：
rand=randint（2，n-2）
x=兰特**d%n#违规行
如果x==1或x==n-1：
持续
对于范围内的r：
返回=真
x=功率（x，2，n）
如果x==1：
返回错误
如果x==n-1：
返回=错误
打破
如果要返回：
返回错误
返回真值
印刷品（primalityTest（2700643,1））

定时计算示例：

从timeit导入timeit
a=2505626
d=1520321
n=2700643
def testA（）：
打印（a**d%n）
def testB（）：
打印（pow（a、d、n））
打印（“时间：%（time）fs”%{“time”：timeit（“testA（）”，setup=“from\uuuu main\uuuu导入testA”，number=1）}）
打印（“时间：%（time）fs”%{“time”：timeit（“testB（）”，setup=“from\uuuu main\uuuu导入testB”，number=1）}）

输出（使用PyPy 1.9.0运行）：

2642565
时间：23.785543秒
2642565
时间：0.000030s

输出（使用Python 3.3.0和2.7.2运行时返回非常相似的时间）：

2642565
时间：14.426975秒
2642565
时间：0.000021s

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