mersenneforum.org Divertimento
 Register FAQ Search Today's Posts Mark Forums Read

 2021-06-20, 00:22 #12 paulunderwood     Sep 2002 Database er0rr E7916 Posts Extra gcd This test looks good: Code: { tst(n,r)=local(t=lift(Mod(2,n)^r)); gcd(t^2-1,n)==1&& gcd(2*t-1,n)==1&& kronecker(1-4*t,n)==-1&& Mod(2,n)^((n-1)/2)==kronecker(t,n)&& Mod(Mod(x,n),x^2-(1/t-2)*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 2021-06-20 at 17:11 Reason: Reinstated extra gcd due to programming error.
2021-06-20, 05:04   #13
paulunderwood

Sep 2002
Database er0rr

3·5·13·19 Posts
Efficent Test

Quote:
 Originally Posted by paulunderwood Again t=1/2^r for small r makes the Lucas PRP test efficient.
The efficient test is:

Code:
{
tst(n,r)=local(t=lift(Mod(1/2,n)^r));
gcd(t^2-1,n)==1&&
gcd(t-2,n)==1&&
kronecker(t^2-4*t,n)==-1&&
Mod(2,n)^((n-1)/2)==kronecker(t,n)&&
Mod(Mod(x,n),x^2-(t-2)*x+1)^((n+1)/2)==kronecker(t,n);
}
To increase the efficiency further a strong 2-PRP test and a strong Lucas test can be used.

I'll be moving over to GMP from Pari/GP to test quickly for pseudoprimes, using Feitsma's 2-PRP list.

EDIT: pseudoprime counterexample is [n,r]=[1351126261,2344]

Last fiddled with by paulunderwood on 2021-06-20 at 17:17 Reason: Had to insert extra gcd

2021-06-20, 17:33   #14
paulunderwood

Sep 2002
Database er0rr

3·5·13·19 Posts

Quote:
 Originally Posted by paulunderwood Here I test over x^2-x+2^r where kronecker(1-4*2^r,n)==-1 x^2-x-2^r where kronecker(1+4*2^r,n)==-1 gcd(2^(2*r)-1,n)==1 8<------- snip
I have verified this for all r for all n<10^11.

I will convert to GMP soon.

Last fiddled with by paulunderwood on 2021-06-20 at 17:41

 2021-06-21, 16:48 #15 paulunderwood     Sep 2002 Database er0rr 3·5·13·19 Posts 1+2 selfridges Based on x^2-2^r*x+-4 ... If n%4==1 then: Code: { tst(n,r)=local(t=lift(Mod(2,n)^r)); gcd(t^2-4,n)==1&& kronecker(t^2-16,n)==-1&& Mod(2,n)^(n-1)==1&& Mod(Mod(x,n),x^2-(t^2/4-2)*x+1)^((n+1)/2)==1; } and if n%4==3 then: 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)^(n-1)==1&& Mod(Mod(x,n),x^2+(t^2/4+2)*x+1)^((n+1)/2)==-1; } Edit: I should have known the same n%4==1 number given in post #13 fails: [n,r]=[1351126261,94] 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 2021-06-21 at 20:40
 2021-06-21, 20:49 #16 paulunderwood     Sep 2002 Database er0rr 1110011110012 Posts base 3 variant This time based on x^2-3^r*x+-9 ... n%4==1: Code: { tst(n,r)=local(t=lift(Mod(3,n)^r)); gcd(t^2-3,n)==1&&gcd(t^2-9,n)==1&& kronecker(t^2-4*9,n)==-1&& Mod(3,n)^(n-1)==1&& Mod(Mod(x,n),x^2-(t^2/9-2)*x+1)^((n+1)/2)==1; } n%4==3: Code: { tst(n,r)=local(t=lift(Mod(3,n)^r)); kronecker(t^2+4*9,n)==-1&& Mod(3,n)^(n-1)==1&& Mod(Mod(x,n),x^2+(t^2/9+2)*x+1)^((n+1)/2)==-1; } No luxury of Feitsma's list here, instead relying on Pari/GP's ispseudoprime(). Deep searching will require GMP+PrimeSieve. 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 2021-06-21 at 21:13
 2021-06-21, 23:34 #17 paulunderwood     Sep 2002 Database er0rr 3·5·13·19 Posts Only x^2-2^r*x-4 Based on only x^2-2^r*x-4 ... 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)^(n-1)==1&& Mod(Mod(x,n),x^2+(t^2/4+2)*x+1)^((n+1)/2)==kronecker(-1,n); } Verified for n<1.5*10^10 Last fiddled with by paulunderwood on 2021-06-21 at 23:43