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

13·172 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

72558 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

13×172 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

13×172 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

13×172 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

13·172 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
Old 2021-06-23, 18:29   #18
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

72558 Posts
Default

GMP is an order quicker than Pari/GP for this task. I have attached my GMP code. Note that it misses out x^2-x-4, but it would take a minute to test this special case with Pari/GP.

I fixed that anomaly by using a repeat-until construct instead of while-do, and have uploaded the new code.

Oops the edit was not functioning. Code reverted.
Attached Files
File Type: c neg4_2_r.c (3.0 KB, 9 views)

Last fiddled with by paulunderwood on 2021-06-23 at 21:08
paulunderwood is offline   Reply With Quote
Old 2021-06-25, 12:39   #19
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

72558 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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);
}
I have tested n < 3*10^11.

If r=1 the this test is the same as the $620 quest given on this page which purports to have around 740 counterexamples chosen from products of a powerset of 1248 primes

Last fiddled with by paulunderwood on 2021-06-25 at 12:50
paulunderwood is offline   Reply With Quote
Old 2021-06-25, 21:25   #20
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110101011012 Posts
Default

I am slightly change the last test for practical purposes

Code:
{
tst(n,r)=local(t=lift(Mod(2,n)^r));
if(n==2||n==3||n==5,return(1));
if(gcd(30,n)!=1||issquare(n),return(0));
((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 now using GMP for n<4.2*10^11

EDIT: There are 2-PSPs for which kronecker(t^2+16,n) are never equal to -1.

Last fiddled with by paulunderwood on 2021-06-26 at 20:33
paulunderwood is offline   Reply With Quote
Old 2021-06-26, 20:32   #21
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

13×172 Posts
Default Fibonacci

Back to the drawing board...

Restrict n to 3 or 7 mod 20. Then x^(n+1) == -b^2 (mod n, x^2-b*x-b^2) can be transformed into x^((n+1)/2) == -1 (mod n, x^2+3*x+1) and b^(n-1) == 1 (mod n). I am now checking this out with gcd(b^6-1,n)==1.

Here is code I am using;

Code:
{
}for(n=1,100000000000,
if((n%20==3||n%20==7)&&!ispseudoprime(n)&&Mod(Mod(x,n),x^2+3*x+1)^((n+1)/2)==-1,
for(b=2,(n-1)/2,
if(Mod(b,n)^(n-1)==1,
print([n,b,gcd(b^6-1,n)])))))
}

Last fiddled with by paulunderwood on 2021-06-26 at 21:28 Reason: changed to gcd(b^6-1,n)==1
paulunderwood is offline   Reply With Quote
Old 2021-06-27, 21:38   #22
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

13·172 Posts
Default Only x^2-2^r*x-2

Just when I was about to give up on this thread I have a great test based on x^2-2^r*x-2, which can be transformed into

Mod(-2,n)^((n-1)/2)==kronecker(-2,n)
Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n)

On running the following code through Feitsma's 2-PSP list I see an amazing pattern:

Code:
{
for(v=1,#V,n=V[v];
if(Mod(-2,n)^((n-1)/2)==kronecker(-2,n),
z=znorder(Mod(2,n));
for(r=1,z,
t=lift(Mod(2,n)^r);
if(Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n),
print([n,gcd(t^2+2,n),z,r,t])))))
}
Output begins:

Code:
[357761, 357761, 130, 33, 92982]                                              
[357761, 357761, 130, 98, 264779]
[580337, 580337, 166, 42, 278509]
[580337, 580337, 166, 125, 301828]
[1016801, 1016801, 50, 13, 8192]
[1016801, 1016801, 50, 38, 1008609]
[1325843, 1325843, 166, 42, 1212637]
[1325843, 1325843, 166, 125, 113206]
[1441091, 1441091, 346, 87, 1013827]
[1441091, 1441091, 346, 260, 427264]
[11081459, 11081459, 226, 57, 2832748]
[11081459, 11081459, 226, 170, 8248711]
[13057787, 13057787, 466, 117, 396142]
[13057787, 13057787, 466, 350, 12661645]
[13338371, 13338371, 1054, 264, 8365567]
[13338371, 13338371, 1054, 791, 4972804]
[15479777, 15479777, 586, 147, 2696885]
[15479777, 15479777, 586, 440, 12782892]
[17134043, 17134043, 274, 69, 4719826]
[17134043, 17134043, 274, 206, 12414217]
[19607561, 19607561, 586, 147, 9598831]
[19607561, 19607561, 586, 440, 10008730]
[23577497, 23577497, 1618, 405, 12240097]
[23577497, 23577497, 1618, 1214, 11337400]
[30740417, 30740417, 826, 207, 21836230]
[30740417, 30740417, 826, 620, 8904187]
[31436123, 31436123, 1618, 405, 22995114]
[31436123, 31436123, 1618, 1214, 8441009]
[53695721, 53695721, 130, 33, 52314953]
[53695721, 53695721, 130, 98, 1380768]
[59840537, 59840537, 2578, 645, 45404751]
[59840537, 59840537, 2578, 1934, 14435786]
[79786523, 79786523, 2578, 645, 12638556]
[79786523, 79786523, 2578, 1934, 67147967]
[85519337, 85519337, 3082, 771, 73655817]
[85519337, 85519337, 3082, 2312, 11863520]
[97924217, 97924217, 3298, 825, 90289000]
[97924217, 97924217, 3298, 2474, 7635217]
Note that gcd(t^2+2,n) catches, and that r=(z+2)/4 and r=3*(z+2)/4-1 (where z%4==2) provide the cases where the gcds are needed.

But then the pattern is broken by:

Code:
[2139155051, 2139155051, 75650, 18913, 307017169]
[2139155051, 43691, 75650, 22942, 1739818799]
[2139155051, 2139155051, 75650, 56738, 1832137882]
[2139155051, 43691, 75650, 60767, 399336252]

Last fiddled with by paulunderwood on 2021-06-27 at 21:54
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lucas and Fibonacci primes Batalov And now for something completely different 9 2017-06-28 16:56
Lucas Table R.D. Silverman Factoring 19 2012-09-07 17:24
Need help with Lucas Sequences... WraithX Programming 11 2010-09-23 23:22
Lucas-Lehmer Test storm5510 Math 22 2009-09-24 22:32
Lucas-Lehmer Dougal Information & Answers 9 2009-02-06 10:25

All times are UTC. The time now is 22:13.


Thu Jul 29 22:13:16 UTC 2021 up 6 days, 16:42, 1 user, load averages: 2.11, 2.09, 2.14

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.