Sorry, an error occurred while loading the content.

## Two parameter PRP test

Expand Messages
• 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
Message 1 of 2 , Aug 4, 2013
• 0 Attachment
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
• ... That seems like a fair 6-Selfridge double-Lucas test with two free parameters. So it ought to be foolable by choosing a pair of appropriate cosines.
Message 2 of 2 , Aug 4, 2013
• 0 Attachment
--- In primenumbers@yahoogroups.com, "paulunderwooduk" <paulunderwood@...> wrote:

> am I cheating?

> {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;}

That seems like a fair 6-Selfridge double-Lucas test
with two free parameters. So it ought to be foolable
by choosing a pair of appropriate cosines.

However, you have used up your monthly credit,
so expect counterexamples from the Gremlins in
September.

David
Your message has been successfully submitted and would be delivered to recipients shortly.