Conference rusure::math

962.0. "Probabilistic Primality Testing." by ERLTC::COOPER (Topher Cooper) Mon Oct 31 1988 14:52

I thought the following was interesting and possibly useful.  I am
cross-posting it to the MAPLE conference.

					Topher

Newsgroups: sci.math.symbolic
Path: decwrl!sun!pitstop!sundc!seismo!uunet!mnetor!utzoo!utgpu!water!watmath!watdragon!ghgonnet
Subject: Heuristic primality testing
Posted: 30 Oct 88 03:23:08 GMT
Organization: U of Waterloo, Ontario
 
 
		Heuristic primality testing
		********* ********* *******
 
Maple uses a probabilistic primality test.  From time to time we
receive inquires about how ``safe'' this probabilistic test really
is.  The algorithm for heuristic primality testing used by Maple
differs very little from the probabilistic test proposed by Knuth
(The Art of Computer Programming, Vol 2, Ch 4.5.4, algorithm P).
 
The algorithm works as follows:  for testing whether  n  is a prime,
compute  q  odd, such that n = 1 + q*2^k.  Compute b^(n-1) (mod n)
(this can be done quickly with binary powering).  If it is not equal
to 1, n is composite.  If it is 1, compute  b^q, b^(2q), ... b^(n-1).
Each term of the sequence is the square of the previous one.  Scanning
from right to left, the first non-1 should be congruent to -1, if it
is not, then  n  is not prime.  Repeat this test with randomly chosen
b's.
 
Maple's isprime() checks for any prime factor less than 1000 and then
performs 5 iterations of the above algorithm, not for random b's
but for b = 2,3,5,7,11.  (The number of iterations can be altered by
specifying a second argument).
The interesting mathematical question is then:  How often does
this test fail for 1 iteration?  for 2?  for 5 (the default)?
I.e. how many composite numbers, with no factors less than 1000
satisfy the above algorithm for b = 2, or b=2,3 or etc.
 
Of course, exhaustive search is out of the question, but there
are a few observations which make the search for failures much
easier.
 
if 2^(n-1) = 1 (mod n) and n = p*q (p prime) then
 
   2^(n-1) = 1 (mod p) and
 
let phi2(p) the smallest integer greater than 0 such that
2 ^ phi2(p) = 1 (mod p)  then
 
	phi2(p) | (n-1)   -->  p*q == 1 (mod phi2(p))
	q == (1/p) (mod phi2(p))
 
which means that for every prime p > 1000, we need to do a linear
scan of values of q with step  phi2(p).  (All the above values
are ``easy'' to compute).
 
The smallest composite number satisfying one iteration is:
 
	1,194,649 = 1093^2  and the second is
	1,678,541 = 1013*1657.
 
There are 32 such integers between 10^6 and 10^7, which gives an
extremely low density of numbers which fail the first iteration.
The density (apparently) decreases as  n  increases.
 
The smallest composite number satisfying two iterations is:
 
	2,284,453 = 1069*2137
 
the smallest satisfying 3 iterations is:
 
        25,326,001 = 2251 * 11251
 
the smallest satisfying 4 iterations (under a comprehensive but
not exhaustive search) is:
 
        118,670,087,467 = 172243 * 688969
 
all the numbers we found satisfying five iterations are:
 
        11,377,272,352,951 = 1686511 * 6746041
        18,996,486,073,489 = 1949179 * 9745891
        21,569,059,132,741 = 3283981 * 6567961
        22,749,134,240,827 = 2384803 * 9539209
        29,578,828,517,101 = 3845701 * 7691401
        40,682,698,620,481 = 3682513 * 11047537
        49,550,735,135,449 = 3148039 * 15740191
 
and six iterations (ditto):
 
        32,398,013,051,587 = 2845963 * 11383849
 
The number of composites which satisfy the test for one
iteration are, at least:
 
between 10^6 .. 10^7       32
	10^7 .. 10^8      203
        10^8 .. 10^9      569
	10^9 .. 10^10    1454
       10^10 .. 10^11    3847
       10^11 .. 10^12    9108
 
These numbers, per range, clearly grow, while the density
clearly decreases.
 
The total number of composite numbers which we found pass 2, 3,
4, etc. iterations are:
 
	2 iters     3 iters     4 iters     5 iters     6 iters
          5659        423          49          7           1
ratios          13.4         8.6         7           7
(theoretically, the ratio is >= 4).
 
Curiosities/observations:
 
  (1) The first observation is that although the probability of
a composite number passing one iteration is, in practice,
extremely small, the probability of a composite number which
passes k iterations passing k+1 iterations is not small at
all (these experiments suggest that it may approach the theoretical
limiting value of 1/4).
 
  (2) In all our tests no square satisfied more than one iteration
(and only two squares 1093^2 and 3511^2 were found to satisfy one
iteration in all our testing).
 
  (3) The most important observation is perhaps that the ratios
between phi(p.i) and phi(p.j), where p.i and p.j are factors of
the above numbers, are very small fractions, or in other words,
the phis of the prime factors have very large gcds.  This is not
very surprising, but I do not know if anything can be demonstrated
about it.  For example, for the numbers which satisfy 5 or 6
iterations, the ratios (p2-1)/(p1-1) (all of these have only
two prime factors) are 2,3,4 or 5.
 
This latter observation suggests a complementary test for primality,
which I think is the most valuable conclusion of this exercise:
 
	After trying and succeeding with 5 iterations of Knuth's
	algorithm, try whether
 
                     2         1/2 
         (1 - 2 k + k  + 4 k n)    - 1 - k
       -------------------------------------  divides n
                       2 k                  
	or
		ceil( sqrt(n/k) )  divides  n
 
	for a few values of k (e.g. k = 2,....,100, 3/2,...,19/2)
 
This composite algorithm appears much more robust than just
trying more iterations of the original one.
 
					Gaston H. Gonnet