Divertimento -- Four Lucas Tests

[paulunderwood]

Based on a Lucas PRP test over x^2-b^r*x+b, I have come up with a general test:

{tst(n,b,r)=local(t=lift(Mod(b,n)^(2*r-1)));
kronecker(b,n)==-1&&
kronecker(t-4,n)==1&&
gcd(t-3,n)==1&&
gcd(t-2,n)==1&&
gcd(t-1,n)==1&&
gcd(r-1,n-1)==1&&
Mod(b,n)^((n-1)/2)==-1&&
Mod(Mod(z,n),z^2-(t-2)*z+1)^((n+1)/2)==-1;}

Testing is slow with 3 nested loops. Can you find a counterexample?

Edit: I just noticed this test does not work for primes 3, 5, 7, 17, 23 and 31. Bigger primes have plenty of scope given by the parameters.

I made a programming error in Pari/GP, taking a gcd of a fraction when coding the above in a different way. So the above script easily gives counterexamples. Oh well!

[paulunderwood]

I have now devised a general test of the polynomial x^2-b^r*x+b with an Euler PRP test for the discriminant b^(2*r)-4*b:

{tst(n,b,r)=local(t=lift(Mod(b,n)^(2*r-1)),k=kronecker(b,n));
gcd(b,n)==1&&
gcd(t-1,n)==1&&
gcd(t-2,n)==1&&
gcd(t-3,n)==1&&
kronecker(t-4,n)==-k&&
Mod(b,n)^((n-1)/2)==k&&
Mod(t-4,n)^((n-1)/2)==-k&&
Mod(Mod(z,n),z^2-(t-2)*z+1)^((n+1)/2)==k;}

(I think that is coded up properly).

Can you fool this 1+1+2 Selfridge "restricted domain" PRP test?



Edit: I found some frauds for n=287051.

Because 2 appears as the denominator for the solution to x I have added a Fermat base 2 PRP test and am trying to find a pseudoprime to this new test.

Edit 2: A counterexample is tst(79786523,206932265,1)