mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-06-20, 00:22   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E7916 Posts
Cool 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.
paulunderwood is offline   Reply With Quote
Old 2021-06-20, 05:04   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·5·13·19 Posts
Thumbs up Efficent Test

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-06-20, 17:33   #14
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·5·13·19 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2021-06-21, 16:48   #15
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·5·13·19 Posts
Smile 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
paulunderwood is offline   Reply With Quote
Old 2021-06-21, 20:49   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110011110012 Posts
Lightbulb 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
paulunderwood is offline   Reply With Quote
Old 2021-06-21, 23:34   #17
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3·5·13·19 Posts
Cool 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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 15:37.

Wed Jun 23 15:37:35 UTC 2021 up 26 days, 13:24, 0 users, load averages: 2.08, 2.16, 2.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.