interesting synopsis! actually, the statistical independence has been pointed out before, in the "lucas pseudoprimes" paper by baillie and wagstaff. in fact, it seems to be "better" than mere independence: the two types of pseudoprimes appear to avoid each other. you might also find this interesting: "TWO CONTRADICTORY CONJECTURES CONCERNING CARMICHAEL NUMBERS" by granville and pomerance. also, "on the distribution of pseudoprimes" by pomerance. basically, there are heuristic arguments for the number of carmichaels psp's,, etc., up to x being > x^.99 (for ridiculously large x). it seems unlikely that O(1) psp tests would suffice; the number of tests you do should increase (slowly?) as N increases. however, it also seems that only a small number of tests gives pretty good results. bob baillie ------------------- Warren Smith wrote:
Let N>10 be an odd integer we wish to test for primality. Let N = v * 2^s + 1 where s>0 and v>0 are integers.
0. Trial division by 2,3,5,7,11,... is useful as a quick screen to spot easy composites, but ultimately is extremely inefficient.
1. The following primality test is well known: Miller-Rabin et al "strong A-pseudoprime test": Let A be a constant with 0<A<N and GCD(A,N)=1. [If GCD>1 then we have found a factor of N and can quit now.] Compute J=A^v mod N. If |J|=1 then output "N probably prime" and stop. Now square J (mod N) repeatedly up to s-1 times; if ever J=-1 then output "N probably prime" and stop. Finally, output "N is definitely composite."
This test is known to fail (i.e. say "probably prime" when in fact N is composite) for less than 1/4 of the A's chosen randomly mod N with GCD(A,N)=1, but for most N fails much less often, e.g. Pomerance, Selfridge, Wagstaff found that there were only 13 cases (which they tabulated) among the 2<N<25*10^9 that simultaneously failed the three tests with A=2,3, and 5, and all 13 happened to have the form N=(k+1)*(r*k+1) for r in the set {2, 3, 4, 5, 7} except for N=397*4357*8317 which has the form N=(k+1)*(208*k+1). These special forms could be detected (and hence N factored) by solving quadratic equations for k.
The least N which simultaneously fails the 7 tests based on A=2,3,5,7,11,13,17 is N=(k+1)*(3*k+1) where k=10670053; this N is 3.4*10^14 approximately. This indicates these 7 tests could be crudely regarded as acting as though they were "independent with failure probability 1/119 each."
Three tests using A=2, 7, and 61 suffice for all N<4759123141.
2. E.Lucas followed by R.Baillie & S.S.Wagstaff had an idea which I shall regard as similar to the above, but now the quantity A being exponentiated mod N is a 2x2 matrix, not a scalar. Specifically,let A be [ P 1 ] [ -Q 0 ] where P>0 and Q are integers chosen so that 0<=P,Q<N and D=P*P-4*Q is nonzero and GCD(N,Q)=1 and GCD(N,D)=1, and JacobiSymbol(D|N) = -1. Compute J=A^v mod N. If the top left entry of J is 0, then N is a "probable prime" and stop. Now for each k with 0<=k<s do{ if the first entry of (P,2)*J is 0, then{ output "N is a probable prime" and stop} square J. } If we reach here, "N is definitely composite."
It is known that at most 4/15 of the possible random choices of P,Q can cause failure [F.Arnault: Math. Comput. 66,218 (1997) 869-881] unless N=(k-1)*(k+1) which could be detected by testing N+1 for squareness... (and even for these N failure probability<1/2) but for most N failures are much rarer.
Usually Lucas failures are of the form N=(k-1)*(r*k+1) for r in the set {1,2,3,4,5} or of the form N=(k+1)*(r*k-1) for r in the set {2}, or N=(k+1)*(r*k-1) for r in the set {2,4,6,20}.
Again, it is possible to detect and factor N of these specially likely to be bad forms, by solving quadratics for k. A simpler idea is simply finding sqrt(N/m) for m=1,2,3,... and if any of these result in values very close to integers, then test integers near these square roots as possible factors of N.
Furthermore, although in the Miller-Rabin test failure for some A makes failure for other A much more likely, Miller-Rabin and Lucas failures tend to behave like statistically independent events; the reason for that, which apparently has not been pointed out before, is the pretty much disjoint natures of the bad-N sets discussed above.
Pomerance, Selfridge & Wagstaff offerred $620 for anybody finding a composite N (congruent to +-2 mod 5) such that N is a Miller-Rabin pseudoprime with A=2 *AND* N is a Lucas pseudoprime with P=1, Q=-1 (or prove none exist). The prize is uncollected. Apparently Jeff Gilchrist has shown there are no such N below 10^17.
The Miller-type primality test produces as a side effect, knowledge that certain numbers A are square or nonsquare mod N, This knowledge can be used to produce parameters for use in a Lucas-type test, thus saving time when doing combined tests. I have not seen that pointed out before either.
3. R.Perrin, followed by Wm.Adams & Daniel Shanks, suggested another test which can be viewed as based on exponentiating 3x3 matrices. Wm Adams & Daniel Shanks: Strong PrimalityTests That Are Not Sufficient, Maths of Comput 32 (1982) 255-300
GC Kurtz, D.Shanks, H.C.Williams: Fast Primality Tests for Numbers Less Than 5*10^10, Maths of Comput 46,174 (1986) 691-701 http://www.ams.org/journals/mcom/1986-46-174/S0025-5718-1986-0829639-7/S0025...
The Adams-Shanks test involves these two 3x3 matrices A= [ r -s 1 ] [ 1 0 0 ] [ 0 1 0 ] and Ainverse= [0 1 0] [0 0 1] [1 -r s]. They study (r,s) = (0,-1) Perrin (r,s) = (1,0) "Secundo" (r,s) = 1,-1) (r,s) = -1,-2).
4. Retrospective. All these matrix exponentials mod N, can also be viewed as polynomial(x) exponentials modulo both a fixed polynomial and mod N. This polynomial-based view of it is probably better, and it ultimately succeeded in yielding the rigorous AKS primality test. AKS involves polynomials of degree up to of order (logN)^2, or equivalently matrices of size up to order (logN)^2 x (logN)^2.
Jon Grantham has given an excellent survey of this all that unifies everything using the polynomial view, he calls it "Frobenius pseudoprimes": http://www.pseudoprime.com/pseudo1.ps
I suspect, however, that AKS is overkill. First of all, I suspect that O(logN) tests similar to Miller and Lucas suffice to get the failure rate so low than only a finite number of bad N exist (which could be listed in a finite size lookup table) -- because this in fact is true if random A are used in Miller's tests, and hence some fast deterministic choice of the A's as a function of N ought to work if there is any justice.
If we were really smarter then perhaps we could show only O(1) tests suffice.
My reason for the second suspicion is this. Suppose we could argue that the only N which fail some such test, need to be Carmichael numbers or anyhow something like them with at least 3 factors and with the factors having a specific form, OR if there are 2-factor baddies, see below. It is fairly clear from computer output there are about N^(1/3+o(1)) Carmichael numbers up to N although the rigorous count bounds on them are considerably weaker. I.e. the "probability density" of bad N would be about N^(o(1)-2/3) for those kind of N. Then if we had two tests which were *independent* the density of *doubly* bad N would be about N^(o(1)-4/3), which is fast enough falloff to get only a finite set of bad N in all.
Further if the 2-factor baddies by means of quadratic-solving for specific common forms could be made rare enough to have density below N^(-1/2) * (logN)^(-K) for some constant K>0.5, then the doubly-bad N would have density below N^(-1) * (logN)^(-2*K) which would be low enough to assure only a finite set of doubly-bad N existed.
But on the other hand...
Erdos has conjectured that eventually, the number of Carmichaels below N will exceed N^0.99. It has never been observed to exceed N^0.4 so far, but Erdos says to hell with the computer evidence since his ideas only kick in for N with huge numbers of prime factors. Anyhow, if Erdos is correct, then my above flaky density arguments are destroyed.
More precisely, Erdos conjectured the number of Carmichaels and pseudoprimes below N ultimately behaves like N^(1 - constant*lnlnlnN / lnlnN) and upper bounds of this kind have been proven. If Erdos is right then even if all the Miller-esque and Lucas-esque and etc test failures acted "independent" then the best we could hope to hope for would be that about lnlnN / lnlnlnN tests would be needed.
That's bigger than O(1), but a lot smaller than O(logN).