Chapter 23 – Finding Prime Numbers 361FINDING PRIME NUMBERS
Topics Covered In This Chapter:
Prime and Composite Numbers
The Sieve of Eratosthenes
The Rabin-Miller Primality Test
“Mathematicians have tried in vain to this day to
discover some order in the sequence of prime
numbers, and we have reason to believe that it is a
mystery into which the human mind will never
penetrate.”Leonhard Euler, 18th century mathematician
All of the ciphers described in this book so far have been around for hundreds of years, and all of
them (with the exception of the one-time pad) are easily broken by computers. These ciphers
worked very well when hackers had to rely on pencil and paper to hack them, but computers can
now manipulate data trillions of times faster than a person with a pencil.
The RSA cipher has several improvements over these old ciphers, and it will be detailed in the
next chapter. However, the RSA cipher will require us to learn about prime numbers first.