Miller Rabin 测试慢速 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)

这比朴素的方法进行模幂运算要快得多，因为它在每次乘法时取模，而不是建立一个巨大的数并在之后取模。