374 http://inventwithpython.com/hacking

Email questions to the author: [email protected]

421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
953, 967, 971, 977, 983, 991, 997]
44.

45. if num in lowPrimes:


46. return True

The numbers in the lowPrimes list are primes. (Duh.) We can immediately return True if num
is in the lowPrimes list.

rabinMiller.py

48. 
    

    See if any of the low prime numbers can divide num

    
    


49. for prime in lowPrimes:


50. if (num % prime == 0):


51. return False

Line 49 loops through each of the prime numbers in the lowPrimes list. The integer in num is
modded with the % mod operator by each prime number on line 50, and if this evaluates to 0 then
we know that prime divides num and so num is not prime. In that case, line 51 returns False.

Checking if num is divisible by all the primes under 1000 won’t tell us if the number is prime, but
it might tell us if the number is composite. About 30% of the random numbers that
generateLargePrime() creates that are composite will be detected as composite by
dividing by the low prime numbers. Dividing by the low prime numbers is much faster than
executing the full Rabin-Miller algorithm on the number, so this shortcut can make our program
execute much more quickly.

rabinMiller.py

53. 
    

    If all else fails, call rabinMiller() to determine if num is a prime.

    
    


54. return rabinMiller(num)

Those are all the quick tests to determine if a number is prime or not. But if num does not match
any of those tests, then it is passed to the rabinMiller() function to check if it is prime or
not. The return value of rabinMiller() will be returned by isPrime().

The comment on line 53 means call the rabinMiller() function to determine if the number is
prime. Please do not call Dr. Rabin or Dr. Miller personally to ask them if your number is prime.

rabinMiller.py