Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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.

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
Middle School Prime Numbers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search