Chapter 23 – Finding Prime Numbers 375

57. def generateLargePrime(keysize=1024):


58. 
    

    Return a random prime number of keysize bits in size.

    
    


59. while True:


60. num = random.randrange(2(keysize-1), 2(keysize))


61. if isPrime(num):


62. return num

The generateLargePrime() function will return an integer that is prime. It does this by
coming up with a large random number, storing it in num, and then passing num to isPrime().
The isPrime() function will then test to see if num is composite and then pass the num to
rabinMiller() for a more thorough (and computationally expensive) primality test.

If the number num is prime, then line 62 returns num. Otherwise the infinite loop goes back to
line 60 to try a new random number. This loop keeps trying over and over again until it finds a
number that the isPrime() function says is prime.

Summary

Prime numbers have fascinating properties in mathematics. As you will learn in the next chapter,
they are also the backbone of ciphers used in actual professional encryption software. The
definition of a prime number is simple enough: a number that only has one and itself as factors.
But determining which numbers are prime and which are composite (that is, not prime) takes
some clever code.

Modding a number with all the numbers from two up to the square root of the number is how our
isPrime() function determines if that number is prime or not. A prime number will never have
a remainder of 0 when it is modded by any number (besides its factors, 1 and itself.) But this can
take a while for the computer to calculate when testing large numbers for primality.

The sieve of Erastothenes can be used to quickly tell if a range of numbers is prime or not, but
this requires a lot of memory.

The RSA cipher makes use of extremely large prime numbers that are hundreds of digits long.
The Sieve of Erastothenes and the basic isPrime() function we have in primeSieve.py aren’t
sophisticated enough to handle numbers this large.

The Rabin-Miller algorithm uses some mathematics which has simple code (but the mathematical
reasoning behind it is too complex for this book), but it allows us to determine if a number that is
hundreds of digits long is prime.