Miller Rabin Test Slow Python

Question

因此，我从http://www.javascripter.net/math/primes/miller_rabin_pseudocode.txt，并认为用python编写它会很酷。所以我写了这个：

n = input('Enter a number to test ')
n = int(n)
a=int(5)
d = n - 1
s = 0
while (d % 2 == 0):
   s = s + 1
   d = int(d/2)
x = a**d
x = x % n
if (x==1 or x==(n-1)):
   print("probably prime")
r = int(1)
while(r<(s-1)):
   x = x**2
   x = x%n
   if (x==1):
      print ("composite")
   if (x==(n-1)):
      print ("probably prime")
print("if nothing above is printed n is composite")

它运行得很好，但当我输入六位数时，速度慢得令人难以置信。所以我找到了一些代码http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python，而且它几乎是即时的，即使有大的（10^30）数字。

那么，我在上面的代码中做错了什么，导致它变得如此缓慢呢？

Answer 1

您还应该替换：

x = a**d
x = x % n

带有：

x = pow(a, d, n)

它做模幂运算的速度比天真的方法快得多，因为它在每次乘法时都取模，而不是建立一个巨大的数字并在之后取模。

Answer 2

链接代码中的第二个循环最多只进行5次迭代，而您的循环则执行类似log（n）的操作。

编辑：甚至更多——"r"变量永远不会被修改，因此循环的退出条件永远不会得到满足。退出循环的唯一可能是中断。