"Galois test": new(?) class of compositeness tests based on two polynomials A(x) and B(x) ===========Warren D. Smith-=============January 2012===================================== The following tests are intended to try to further-exploit the observation R.Baillie made that the pseudoprime (failure) sets for the Lucas and Miller type tests, tend to be "better than statistically independent" indeed actually "mutually avoiding." I am going to propose an infinite family of tests based on a pair of degree-k polynomials. It is infinite because k=2,3,4,5,... are all possible. In the case k=2 the test is pretty much like the Lucas test. There is no case k=1, but we will just say as a special case that k=1 is the Miller-Rabin/Fermat test, since that is the spirit if not the letter of the law. These tests can probably be improved to make them "strong" in the same way Miller-Rabin improved the simple Fermat test to make it "strong." However, I have not thought about that and will only present the "weak" tests here. THE SCENARIO: Let N>10, N odd, be a number we want to test for primality. Let k>1 be a small integer. THE "DEGREE-k GALOIS TEST": 1. Generate suitable random polynomials A(x) and B(x). B(x) being "suitable" means: * degree(B)=k * Coefficients of B are integers mod N * B is monic (i.e. coefficient of x^k is 1) * GCD(N, B(0)*discriminant(B(x),x)) = 1 [if not, then N is factored and we're done], Simpler criteria could be used here is you do not want to program discriminants, i.e. just B(0) is nonzero with GCD(B(0), N)=1 suffices. Discriminants might matter in a future "strong" version of this, though. * B(x) is "pseudo-irreducible" mod N, i.e. passes the irreducibility test below which would if N were prime be a proof of irreducibility. 2. The irreducibility test I had in mind is M.Ben-Or's [SFOCS 22 (1981) 394-398]: for j=1..floor(k/2) do{ G(x) = PolynomialGCD( B(x), x^(N^j) mod B(x) - x ) mod N; if G(x) is not 1 then "B is reducible" and stop; } Conclude "B(x) is irreducible mod N." This is valid if N is prime. [Note inside the loop you can repeatedly keep raising the power of x you had before, to the Nth power.] 3. Now, once you've produced A(x) and B(x) (by random trial) meeting the above conditions, we are ready to test N: for j=k-1 down to 1 do{ If PolynomialDegree( A(x)^((N^k-1)/(N^j-1)) mod B(x) mod N ) >= j then "N is definitely composite" & stop. } 4. Loop back to step 1. 5. If survive enough loop iterations of steps 1-4 then "N is probably prime." RUNTIME: If N is prime, then the fraction of random poolynomials which are irreducible is known to be >=1/k. Hence <=k random trials of steps 1-2 should suffice on average to find a suitable B(x). Ditto for A(x). Reviewing the exclusion argument underlying this, it seems to me that if N is composite then this runtime upper bound can only become more true. So the entire test is polynomial expected time and comparable to O(k^3) Miller-Rabin tests if we use "slow" polynomial arithmetic. And more like O(k^2.01) using "fast." [In practical use I think k would be small like k=2,3,4,5 only.] WHY IT WORKS: If N is prime, then the polynomials modulo N modulo any monic irreducible B(x) of degree(B)=k form the Galois field with N^k elements. The N^k-1 nonzero elements form a *cyclic* multiplicative group (theorem of Galois). Hence raising anything nonzero to power N^k-1 mod B(x) mod N has to yield 1. (Which our step 3 did not bother to test, but one could add that test if wanted.) Also, the cycle must include the entire subgroup of N-1 nonzero scalars, of N^2-1 nonzero polynomials of degree<=1, of N^3-1 nonzero polynomials of degree<=2, etc. Hence anything nonzero raised to the power (N^k-1)/(N^j-1) mod B(x) mod N has to yield a member of this (N^j-1)-element subgroup. I'm only particularly interested in the test with j=1, but since doing all the other tests with j=2,3,...,k-1 can also be done at basically no extra cost as a side effect of doing the test with j=1, I threw them in too. THE EXPONENT: Define E = E(k,N) = N^(k-1)+N^(k-2)+...+N^2+N+1 = (N^k-1)/(N-1). For example E(3,7)=7^2+7+1=57. This is the exponent used in the test with j=1 that I'm most interested in. CAN THIS BE MADE "STRONG"? It we understood nonscalar squareroots of scalars then if E=v*2^s with v odd we could examine the exponents v, 2v, 4v, 8v,..., E, to see if they met stronger criteria. THE HOPE FOR INDEPENDENCE/AVOIDANCE: My intent/hope/conjecture in designing this test is that degree-2 and degree-3 Galois tests and the Miller test all ought to fail "independently" (or, even better, the failures should "avoid" each other)... indeed hopefully all Galois tests with different k should have "independent/avoiding" bad-N failure sets. The reason for this hope is that (i) the exponents E(k,N) with different k all are going to be relatively prime in general, aside from factors of 2 and (ii) hope seems empirically to be true for k=1 and 2, e.g. there are now claimed after a large computation to be zero failures of one Miller (base=2) test combined with one Lucas/Baillie test for all N<2^64. [This totally is the opposite of the empirical fact that failing a Miller test makes other Miller-failures become MORE likely, i.e. dependence with positive correlation.] If so, then given Erdos's conjectures about pseudoprime counts below N ultimately behaving like N^( 1 - PositiveConstant* lnlnN / lnlnlnN ) it would follow from independence/avoidance conjecture that employing O(lnlnN) Galois tests all with different k's would presumably be strong enough so that only a finite set of bad (composite, but appearing prime) N could exist. This would suggest time equivalent to O((lnlnN)^3.01) Fermat tests suffices to rigorously test primality of N. This is surely beyond hope of proof at present, but (lnlnN)^O(1) is a very impressive conjecture, much stronger than Rabin/Miller's O(lnN) or O(lnN)^2. WHAT IS THE CONNECTION TO GRANTHAM'S "FROBENUS PSEUDOPRIMES"? His Frobenius and my Galois tests seem to have something to do with each other. It looks like mine is substantially faster. He has a "strong" notion, while I have not devised a comparable notion. He has not discussed the "independence/avoidance" hope which was my whole motivation, but he does discuss "Carmichael"esque numbers, proving they must have at least k+2 prime factors. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)