Hi,

David has shown how any combined Fermat/Euler/M-R/Lucas/Frobenius PRP test with at most one Lucas component and one parameter can be fooled. He has also demanded a test with two Lucas components has two parameters. I shall now introduce such a test, but am I cheating?

I will outline half of a one parameter test in "x" firstly. The second half of the test is on "-x".

Please consider the matrix [x,-1;1,-1] which has the characteristic polynomial L^2-(x-1)*L+(1-x). Let P=x-1 and Q=1-x. Then P^2/Q-2==-(x+1). So for jacobi(P^2-4*Q,n)==-1, for odd positive n, I can test (weakly) L^(n+1)==1 (mod n, L^2-(x+1)*L+1) and (x-1)^(n-1)==1 (mod n). With the other half of "-x" and gcd(x,n)==1, I have verified this one parameter PRP test for n < 1.12*10^8, co-prime to 30, and all suitable x.

Now I introduce a second parameter "k", with the matrices [x,-k;k,-k] and [-x,-k;k,-k], and the PRP test with appropriate x and k on n co-prime to 6:

{tst(n,x,k)=gcd(x*k,n)==1&&

kronecker((x+3*k)*(x-k),n)==-1&&

kronecker((x-3*k)*(x+k),n)==-1&&

Mod(x*k-k^2,n)^(n-1)==1&&

Mod(x*k+k^2,n)^(n-1)==1&&

Mod(Mod(1,n)*L,L^2-(x+k)/k*L+1)^(n+1)==1&&

Mod(Mod(1,n)*L,L^2-(x-k)/k*L+1)^(n+1)==1;}

Can anyone find a counterexample?

Paul