Introduction to Computers : IDC101

There are some interesting primality checking algorithms that have two possibilities of outputs:

• n is composite
  
• n is probably prime
  

One such algorithm is Miller-Rabin primality test. (See here)

Algorithm is:

Input #1: n > 3, an odd integer to be tested for primality;
Input #2: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime

write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← ad mod n
   if x = 1 or x = n − 1 then
      continue WitnessLoop
   repeat r − 1 times:
      x ← x2 mod n
      if x = n − 1 then
         continue WitnessLoop
   return composite
return probably prime

Now can someone code it in Python? Are there some non-primes that are returned as probably primes by this test? How fast is this test compared to other traditional algorithms?

Keep Pythoning!