Miller Rabin测试慢Python

Question

因此，我从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")

它运行得很好，但我一进入六位数，它就非常慢。所以我找到了一些test#Python代码，它几乎是即时的，即使是大(10^30)个数字。

那么，我在上面的代码中做错了什么，使它慢得多呢？

Answer 1

您还应替换：

x = a**d
x = x % n

通过以下方式：

x = pow(a, d, n)

它比朴素方法做模指数要快得多，因为它在每乘时都取模，而不是建立一个正态数，然后取模数。

Answer 2

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

编辑:甚至更多- "r“变量从未被修改过，因此循环的退出条件永远不会被满足。退出循环的唯一可能性是中断。