372 http://inventwithpython.com/hacking

Email questions to the author: [email protected]

Sample Run of the Rabin Miller Module

If you run the interactive shell, you can import the rabinMiller.py module and call the functions
in it. Try typing the following into the interactive shell:

import rabinMiller
rabinMiller.generateLargePrime()
1228811683422110410305236835154432390074842906007015553694882717483780547440094
6375131251147129101194573241337844666680914050203700367321105215349360768161999
0563076859566835016382556518967124921538212397036345815983641146000671635019637
218348455544435908428400192565849620509600312468757953899553441648428119
rabinMiller.isPrime(45943208739848451)
False
rabinMiller.isPrime(13)
True

How the Program Works..........................................................................................................................................

rabinMiller.py

1. 
   

   Primality Testing with the Rabin-Miller Algorithm

   
   


2. 
   

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

   
   


3. 
   


4. import random

The Rabin-Miller algorithm uses random numbers, so we import the random module on line 4.

The Rabin-Miller Primality Algorithm

rabinMiller.py

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.