python - Miller Rabin Test Slow Python

Question

So, I read the pseudocode from http://www.javascripter.net/math/primes/miller_rabin_pseudocode.txt, and thought it would be cool to write it in python. So I wrote this:

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")

It worked pretty well, but as soon as I got into six digit numbers it was incredibly slow. So I found some code of http://rosettacode.org/wiki/Miller-Rabin_primality_test#Python, and it was almost instant, even with large (10^30) numbers.

So, what did I do wrong int the above code that made it so much slower?

Answer 1

您还应该替换：

x = a**d
x = x % n

和：

x = pow(a, d, n)

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

Answer 2

The second loop in the linked code does only 5 iterations at maximum, whereas your does something like log(n).

EDIT: Or even more - the "r" variable is never modified, so the loop's exit condition will never be satisfied. The only possibility to exit the loop are the breaks.