370 http://inventwithpython.com/hacking

Email questions to the author: [email protected]

The code for this algorithm uses advanced mathematics, and how the algorithm works is beyond
the scope of this book. Like the gcd() function in cryptomath.py, this book will just present the
code for the algorithm for you to use without explanation.

Source Code for the Rabin-Miller Module

Open a new file editor window and type in the following code. Save this file as rabinMiller.py.
This program will be a module that is meant to be imported by other programs.

Instead of typing out the list of numbers on line 43, just temporarily add the lines import
pyperclip and pyperclip.copy(primeSieve(1000)) in the primeSieve.py file and
run it. This will copy the list of primes to the clipboard, and then you can paste it into the
rabinMiller.py file.

Open a new file editor window by clicking on File ► New Window. Type in the following code
into the file editor, and then save it as rabinMiller.py.

Source code for rabinMiller.py

1. 
   

   Primality Testing with the Rabin-Miller Algorithm

   
   


2. 
   

   http://inventwithpython.com/hacking (BSD Licensed)

   
   


3. 
   


4. import random


5. 
   


6. 
   


7. def rabinMiller(num):


8. 
   

   Returns True if num is a prime number.

   
   


9. 
   


10. s = num - 1


11. t = 0


12. while s % 2 == 0:


13. 
    

    keep halving s while it is even (and use t

    
    


14. 
    

    to count how many times we halve s)

    
    


15. s = s // 2


16. t += 1


17. 
    


18. for trials in range(5): # try to falsify num's primality 5 times


19. a = random.randrange(2, num - 1)


20. v = pow(a, s, num)


21. if v != 1: # this test does not apply if v is 1.


22. i = 0


23. while v != (num - 1):


24. if i == t - 1:


25. return False


26. else: