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).

From: Robert Baillie <rjbaillie@frii.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Matrix-Product Primality Tests Message-ID: <4F172BCF.7050804@frii.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed

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.

--The Perrin/Adams-Shanks test based on a 3x3 matrix, really was not doing the right thing from the point of view of getting "independence" or "avoidance" versus earlier tests based on 2x2 and 1x1 matrices. Really, the idea of a pseudoprime test based on a kXk matrix or degree=k polynomial, ought to be to devise the matrix so that exponentiating it to the power N^k-1 (mod something) should deliver 1 if N is a prime because N^k-1 is the order of the cyclic multiplicative group of nonzeros inside the Galois field with N^k elements. In the case k=2, we note N^2-1=(N+1)*(N-1) so we -- if we want to be intelligent -- should contrive things to use the power N+1 and not N-1 which was already covered by scalar tests. Which is exactly what the "true Lucas" tests already do. In the case k=3, note N^3-1 = (N-1)*(N^2+N+1) and Adams+Shanks foolishly (in our view) concentrated on N-1 which was already covered by scalar tests, but really to go for independence/avoidance should have gone for the exponent N^2+N+1. One could continue on to degree k=4. Then N^4-1 = (N^2+1)*(N-1)*(N+1) and we should to be intelligent focus on the exponent N^2+1. It seems plausibly hopeful that by going order by order in this way cooking up a test at each order based on an exponent that in general has GCD<=2 with any preceding exponent, we can keep attaining "independence" or "avoidance" at each level, thus getting an extremely strong combined pseudoprime test. Then based on the Erdos x^0.99 type conjectures combined with independence/avoidance conjectures, going up to k of order lnlnN ought to suffice. The Pomerance/Granville "Two contradictory conjectures" paper Baillie suggested discusses the "x^0.99 Erdos" versus "x^0.5 or less Computer-based" count conjectures for Carmichael numbers below x. They believe in Erdos, but doubt it ever gets above x^0.5 until x>10^100. Their conjectural inequality (2) and their conjecture 1 would basically imply that the $620 combination Miller+Lucas test should have only a small finite set of N that fail it... up until the point where Erdos's reasoning starts to become meaningful, which is probably over-100-digit-long N.