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:
-
Finding Very Small Primes
-
Fermat, Probable-Primality and Pseudoprimes
-
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.
-
341 = 11.31 is a 2-PRP, (Sarrus 1819)
-
91 = 7.13 is a 3-PRP,
-
217 = 7.31 is a 5-PRP and,
- 25 = 5.5 is a 7-PRP.
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.
-
2047 = 23.89 is a 2-SPRP,
-
121 = 11.11 is a 3-SPRP,
-
781 = 11.71 is a 5-SPRP and,
-
25 = 5.5 is a 7-SPRP.
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:
-
If n < 1,373,653 is a both 2 and 3-SPRP, then n is
prime.
-
If n < 25,326,001 is a 2, 3 and 5-SPRP, then n is
prime.
-
If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either
n = 3,215,031,751 or n is prime. (This is actually true for
n < 118,670,087,467.)
-
If n < 2,152,302,898,747 is a 2, 3, 5, 7 and 11-SPRP, then
n is prime.
-
If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11 and 13-SPRP,
then n is prime.
-
If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17-SPRP,
then n is prime.
The first three of these are due to Pomerance, Selfridge and Wagstaff,
the parenthetical remark and all others are due to Jaeschke.
-
If n < 9,080,191 is a both 31 and 73-SPRP, then n
is prime.
-
If n < 4,759,123,141 is a 2, 7 and 61-SPRP, then n
is prime.
-
If n < 1,000,000,000,000 is a 2, 13, 23, and 1662803-SPRP,
then n is prime.
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)