Basic Searching for Prime Numbers
How to Sieve Primes and Examine their Use in Encryption
Mar 27, 2008
A whole number greater than 1 is a Prime Number (or Prime) if it cannot be written as the product of two smaller whole numbers. Thus the first twenty prime numbers are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and 71
None of these have a positive integer divisor other than 1. The number 1 is in a class all by itself and is called the unit.
Finding Primes systematically
The librarian of the great library of Alexandria, Eratosthenes (276-194 B.C.), is mostly remembered for his prime number sieve. A method he used to separate out primes from their common composite companions. Here’s how it works by hand (the scheme is also shown at the top of Figure 1):
- Write down the numbers in order, putting 1 in a box to show that it’s the unit
- Circle the first remaining number, which is 2 and strike out every second number thereafter
- Circle the next remaining number, namely 3, and strike out all subsequent multiples of that number
If one continues this way at each stage, circling the first remaining number and striking its higher multiples, the numbers circled will be prime numbers.
The sieving process is made easier if numbers are written in a tabular array. A software version is available from a German website showing a grid of green coloured numbers. The following procedure should be followed (similar to the above scheme) using Internet Explorer:
- Do not click on the unit (i.e. the number 1)
- Click on the number 2 – all multiples of 2 are greyed out and he number 2 turns red
- Click on the next number 3 – all multiples of 3 are greyed out and the number 3 turns red
Repeat this process by clicking the next available green number in the grid, which will grey out their multiples.
When all prime numbers are found and have turned red, all non-prime multiples will be greyed out and the background of the primes that are left will be changed to deep red with a white font to indicate that the grid has been solved - see the bottom part of Figure 1. This solution is known as “a sieve of Eratosthenes”. To try again, simply refresh the webpage. Note, a larger grid would have more primes to sieve out.
Modern Uses of Prime Numbers
Up until the 19th century, there was little use for prime numbers. Today, very large primes are used for encryption in the computer security industry. To highlight encryption, consider a piece of text that is rewritten by translating each letter in the alphabet by a number of steps, say five steps. The letter E becomes A, the letter F becomes B, and so on… Knowing this algorithm, or key, enables one to retrieve the message.
Cryptographers found that using two prime numbers multiplied together makes a much better key than other common composite numbers, because such a key only has four factors: One, itself, and the two primes that it is a product of. This makes the code much harder to crack.
In general, there is no faster way to crack a code than to find the two prime numbers. For this reason, experts are very interested in making the key large enough to make it extremely difficult to factor.
Very Large Prime Numbers
Some very large primes are called Mersenne Primes and are discussed in another article Searching Mersenne Primes by the author.
 |
 |
