25332Two parameter PRP test
- Aug 4, 2013Hi,
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:
Can anyone find a counterexample?
- Next post in topic >>