20210620, 00:22  #12 
Sep 2002
Database er0rr
E79_{16} Posts 
Extra gcd
This test looks good:
Code:
{ tst(n,r)=local(t=lift(Mod(2,n)^r)); gcd(t^21,n)==1&& gcd(2*t1,n)==1&& kronecker(14*t,n)==1&& Mod(2,n)^((n1)/2)==kronecker(t,n)&& Mod(Mod(x,n),x^2(1/t2)*x+1)^((n+1)/2)==kronecker(t,n); } Again t=1/2^r for small r makes the Lucas PRP test efficient. Last fiddled with by paulunderwood on 20210620 at 17:11 Reason: Reinstated extra gcd due to programming error. 
20210620, 05:04  #13  
Sep 2002
Database er0rr
3·5·13·19 Posts 
Efficent Test
Quote:
Code:
{ tst(n,r)=local(t=lift(Mod(1/2,n)^r)); gcd(t^21,n)==1&& gcd(t2,n)==1&& kronecker(t^24*t,n)==1&& Mod(2,n)^((n1)/2)==kronecker(t,n)&& Mod(Mod(x,n),x^2(t2)*x+1)^((n+1)/2)==kronecker(t,n); } I'll be moving over to GMP from Pari/GP to test quickly for pseudoprimes, using Feitsma's 2PRP list. EDIT: pseudoprime counterexample is [n,r]=[1351126261,2344] Last fiddled with by paulunderwood on 20210620 at 17:17 Reason: Had to insert extra gcd 

20210620, 17:33  #14  
Sep 2002
Database er0rr
3·5·13·19 Posts 
Quote:
I will convert to GMP soon. Last fiddled with by paulunderwood on 20210620 at 17:41 

20210621, 16:48  #15 
Sep 2002
Database er0rr
3·5·13·19 Posts 
1+2 selfridges
Based on x^22^r*x+4 ...
If n%4==1 then: Code:
{ tst(n,r)=local(t=lift(Mod(2,n)^r)); gcd(t^24,n)==1&& kronecker(t^216,n)==1&& Mod(2,n)^(n1)==1&& Mod(Mod(x,n),x^2(t^2/42)*x+1)^((n+1)/2)==1; } Code:
{ tst(n,r)=local(t=lift(Mod(2,n)^r)); gcd(t^2+8,n)==1&& kronecker(t^2+16,n)==1&& Mod(2,n)^(n1)==1&& Mod(Mod(x,n),x^2+(t^2/4+2)*x+1)^((n+1)/2)==1; } I will continue looking for a n%4==3 counterexample. Edit2: n%4=3 has been checked for n<10^11 and now needs GMP treatment. Last fiddled with by paulunderwood on 20210621 at 20:40 
20210621, 20:49  #16 
Sep 2002
Database er0rr
111001111001_{2} Posts 
base 3 variant
This time based on x^23^r*x+9 ...
n%4==1: Code:
{ tst(n,r)=local(t=lift(Mod(3,n)^r)); gcd(t^23,n)==1&&gcd(t^29,n)==1&& kronecker(t^24*9,n)==1&& Mod(3,n)^(n1)==1&& Mod(Mod(x,n),x^2(t^2/92)*x+1)^((n+1)/2)==1; } Code:
{ tst(n,r)=local(t=lift(Mod(3,n)^r)); kronecker(t^2+4*9,n)==1&& Mod(3,n)^(n1)==1&& Mod(Mod(x,n),x^2+(t^2/9+2)*x+1)^((n+1)/2)==1; } Anyway n<10^10 has been verified. The limiting time factor is how big znorder(Mod(3,n)) gets. Edit [n,r]=[1479967201,39104] fools. So it would seem for n%4==1 it is tough to find a reliable test all round. Last fiddled with by paulunderwood on 20210621 at 21:13 
20210621, 23:34  #17 
Sep 2002
Database er0rr
3·5·13·19 Posts 
Only x^22^r*x4
Based on only x^22^r*x4 ...
And it's clunky: Code:
{ tst(n,r)=local(t=lift(Mod(2,n)^r)); ((n%4==1&&gcd(t^2+4,n)==1) (n%4==3&&gcd(t^2+8,n)==1))&& kronecker(t^2+16,n)==1&& Mod(2,n)^(n1)==1&& Mod(Mod(x,n),x^2+(t^2/4+2)*x+1)^((n+1)/2)==kronecker(1,n); } Last fiddled with by paulunderwood on 20210621 at 23:43 