Testing Prime NumbersDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/