|
|
|
Science & Nature
>>
Mathematics
>>
Basic Searching for Prime Numbers
|
Basic Searching for Prime Numbers
How to Sieve Primes and Examine their Use in Encryption
Mar 27, 2008 © Harry P. Schlanger
The Sieve of Eratosthenes is a simple search technique for finding prime numbers. Primes have
been in use only recently, mainly in the computer security industry
The Greek astronomer and mathematician, Eratosthenes (276-194 B.C.), also the appointed librarian of
the ancient library of Alexandria, is mostly remembered for his prime number sieve.
A prime number (or prime) is a whole number greater than 1 and only 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 method Eratosthenes used was to separate out primes from their common composite companions.
Here’s how the
Sieve of Eratosthenes works by hand
(the scheme is also shown in Figure 1 below):
- 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.
Using Software to find Primes
The sieving process is made easier if numbers are written in a tabular array. A German website's
software version
similar to the above scheme but using a browser for display is available. Note, the
preferred browser used should be Internet Explorer, as it has been found that the javascript in
the webpage does not run properly on all browsers.
When the webpage opens with a grid of green
coloured numbers (as per Fig 1), the following procedure is to be adopted:
- 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 Figure 1. This solution is known as
"a sieve of Eratosthenes" and on the webpage, the size of the grid determines the numbers of primes to
sieve out. To try again, simply refresh the webpage.
Modern Uses of Prime Numbers - Cryptography
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.
Readers may be interested in a related article - searching for some very large primes are called
"Mersenne Primes", discussed in
Searching for Mersenne Primes by this author.
The copyright of the article Basic Searching for Prime Numbers is owned by Harry P. Schlanger.
Permission to republish in print or online must be granted by the author in writing.
Figure 1. Prime Number Scheme
Website construction by Gum Leaf Designs © 2009
|
|
Custom Search
Other Articles:
Website Construction:
Gum Leaf Designs © 2009
|
