Testing Prime Numbers

Date: 05/12/2003 at 04:07:48
From: Jackson
Subject: Prime numbers 

Besides the Sieve of Eratosthenes, what other methods can be used to 
determine all prime numbers within a given range? Is there a more 
efficient method?

The Sieve of Eratosthenes seems very inefficient when used as a 
computer algorithm.

Date: 05/12/2003 at 09:14:03
From: Doctor Jacques
Subject: Re: Prime numbers 

Hi Jackson,

There are no really simple algorithms to find prime numbers.

Interestingly enough, it is usually quite simple to prove that a 
number is NOT prime, even without knowing its factors. This method is 
based on Fermat's "Little Theorem," which asserts that, if p is prime 
and a is not a multiple of p:

  a^(p-1) = 1  (mod p)  (*)

So, given a number p, if we can find a number a (called a base) such 
that the above congruence is false, we know that p is not prime. 
Unfortunately, the converse is false: the above congruence can, in 
some cases, be satisfied for some composite numbers p and for all a 
relatively prime with p.

However, the method can be improved - the result is called the "Rabin-
Miller algorithm." With that modification, we use an improved test 
based on (*). For a given composite number p, at most 1/4 of the 
numbers a will pass the test (if p is prime; however, all numbers a 
will pass the test).

This is essentially the "industrial" method of finding primes for 
practical applications, like cryptography. In such a case, to check a 
number p for primality, we execute the test for several different 
bases. If a single test fails, we know that p is not prime. If all 
tests pass, we declare that we accept p as a "probable prime." This 
is not a mathematical proof, but it is considered acceptable for 
practical purposes. Of course, there is a probability of error, but 
it can be made as small as we wish by executing sufficiently many 
tests for different bases. For example, with 100 tests, the 
probability of error is at most one in 2^200 (in practice, it is even 
much lower). By using modular exponentiation techniques, the cost of 
a single test is insignificant.

For some particular numbers, it is possible to prove primality in a 
mathematical sense, but this depends on the numbers. For example, if 
all the prime factors of (p-1) are known (and proven to be prime...), 
it is possible to prove that p is prime, at a very low cost. This can 
provide proof of primality in some cases, but it is not a decision 
method - it will not always produce a proof that a probable prime is 
indeed prime.

Recently, an algorithm has been produced to prove primality in all 
cases. You can read more about this in Eric Weisstein's MathWorld:

   Primality Testing Is Easy - MathWorld Headline News
   http://mathworld.wolfram.com/news/2002-08-07/primetest/ 

There is a link to the original paper at the bottom of the page.

Does this help?  Write back if you'd like to talk about this some 
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/