dalbec/algorithm
Note for users followed by search engine or catalog link. You are inside frameset devoted to obfuscated C programming. This page is a description of algorithm of numerical obfuscation. Web site of author of program is at http://www.utm.edu/research/primes/.

Finding Primes and
Proving Primality

The quick tests

Contents:

  1. Finding Very Small Primes 
  2. Fermat, Probable-Primality and Pseudoprimes 
  3. Strong Probable-Primality and a Practical Test 
 


This is one of four pages on finding primes and proving primality. The first is a short introduction and table of contents. The second (this page) discusses finding small primes and the basic probable primality tests. The third page covers the classical primality tests that have been used to prove primality for 99.9% of the numbers on the largest known prime list. The last page introduces the general purpose tests that do not require factorization.

Note: If you do not see superscripts and subscripts in this sentence,
then click here for a version of this page without super/subscripts.

[contents] 1. Finding Very Small Primes

For finding all the small primes, say all those less than 10,000,000; the most efficient way is by using the Sieve of Eratosthenes (ca 240 BC):
Make a list of all the integers less than or equal to n (greater than one) and strike out the multiples of all primes less than or equal to the square root of n, then the numbers that are left are the primes.
For example, to find all the odd primes less than or equal to 100: list the odd numbers from 3 to 100 (why even list the evens?) The first number is 3 so it is the first odd prime--cross out all of its multiples. Now the first number left is 5, the second odd prime--cross out all of its multiples. Repeat with 7 and then since the first number left, 11, is larger than the square root of 100, all of the numbers left are primes. This method is so fast that there is no reason to store a large list of primes on a computer--an efficient implementation can find them faster than a computer can read from a disk.  

To find individual small primes trial division works okay. Just divide by all the primes less than the square root. For example, to show is 211 is prime, just divide by 2, 3, 5, 7, 11, and 13.

Rather than divide by just the primes, it is sometimes more practical to divide by 2, 3 and 5; then by all the numbers congruent to 1, 7, 11, 13, 17, 19, 23, and 29 modulo 30--again stopping when you reach the square root. This type of factorization is sometimes called wheel factorization. Look in most any elementary text on number theory for information about these tests.

Suppose n has twenty digits, then it is getting impractical to divide by the primes less than its square root, and it is impossible if n has two hundred digits--so we need much faster tests. We discuss several such tests below.

Return to table of contents.

  

[contents]   2. Fermat, Probable-Primality and Pseudoprimes

Fermat's "biggest", and also his "last" theorem states that xn + yn = zn has no solutions in positive integers x, y, z with n > 2. This has finally been proven by Wiles in 1995. What concerns us here is his "little" theorem:
Fermat's (Little) Theorem: If p is a prime and if a is any integer, then ap = a (mod p). In particular, if p does not divide a, then ap-1 = 1 (mod p).
Fermat's theorem gives us a powerful test for compositeness: Given n > 1, choose a > 1 and calculate an-1 modulo n (there is a very easy way to do quickly by repeated squaring. If the result is not one modulo n, then n is composite. If it is one modulo n, then n might be prime so is called a weak probable prime base a (or just an a-PRP). Some early articles call all numbers satisfying this test pseudoprimes, but now the term pseudoprime is properly reserved for composite probable-primes.

The smallest examples of pseudoprimes (composite PRPs) are the following. There are 1,091,987,405 primes less than 25,000,000,000; but only 21,853 pseudoprimes base two, so Henri Cohen joked that 2-PRP's are "industrial grade primes", (It is interesting to note that in 1950 Lehmer, using the weaker definition an = a (mod n) for probable/pseudo-prime, discovered 2*73*1103 = 161038 is an even "pseudoprime" base two.) Richard Pinch lists the pseudoprimes to 1012 (by various definitions) in the PSP directory of his FTP server.

There may be relatively few pseudoprimes, but there are still infinitely many of them for every base a>1, so we need a tougher test. One way to make this test more accurate is to use multiple bases (check base 2, then 3, then 5,...). But we run into an interesting obstacle called the Carmichael numbers.  

Definition: The composite integer n is a Carmichael number if an-1=1 (mod n) for every integer a relatively prime to n.
Here is the bad news: repeated PRP tests of a Carmichael number will fail to show that it is composite until we run across one of its factors. Though Carmichael number are 'rare' (only 2,163 are less that 25,000,000,000), it has recently been shown that there are infinitely many. The Carmichael numbers under 100,000 are
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, and 75361.
Richard Pinch lists the Carmichael's to 1017 at his FTP site.

[contents]   3. Strong Probable-Primality and a Practical Test

A better way to make the Fermat test more accurate is to write n-1 = 2sd where d is odd and s is nonnegative: n is a strong probable-prime base a (an a-SPRP) if either ad = 1 (mod n) or (ad)2r = -1 (mod n) for some nonnegative r less than s.

Again all integers n > 1 which fail this test are composite; integers that pass it might be prime. The smallest odd composite SPRPs are the following.

A test based on these results is quite fast, especially when combined with trial division by the first few primes.

Individually these tests are still weak (and again there are infinitely many a-SPRP's for every base a>1, but we can combine these individual tests to make powerful tests for small integers n>1: The first three of these are due to Pomerance, Selfridge and Wagstaff, the parenthetical remark and all others are due to Jaeschke. Here is the way we usually use the above results to make a quick primality test: start by dividing by the first few primes (say those below 257); then perform strong primality tests base 2, 3, ... until one of the criteria above is met. For example, if n < 25,326,001 we need only check bases 2, 3 and 5. This is much faster than trial division (because someone else has already done much of the work), but will only work for small numbers (n < 341,550,071,728,321 with the data above).

Finally, there is a fair amount more that could (and should) be said. We could discuss Euler pseudoprimes and their relationship with SPRPs. Or we could switch to the "plus side" and discuss Lucas pseudoprimes, or Fibonacci pseudoprimes, or the important combined tests... but that would take a chapter of a book--and it has already been well written by Ribenboim. Let us end this section with one last result:
Millers Test: If the generalized Riemann hypothesis is true, then if n is an a-SPRP for all integers a with 1 < a < 2(log n)2, then n is prime.
The generalized Riemann hypothesis is far too complicated for us to explain here--but should it be proven, then we would have a very simple primality test. Until it is proven, we can at least expect that if n is composite, we should be able to find an a that shows it is composite (a witness) without searching "too" long. (Most surveys cover Miller's test; the improvable constant 2 is do to Bach)