20210620, 00:22  #12 
Sep 2002
Database er0rr
111010110010_{2} 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
2×3^{2}×11×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
2×3^{2}×11×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
2·3^{2}·11·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
3762_{10} 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
EB2_{16} 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 
20210623, 18:29  #18 
Sep 2002
Database er0rr
2·3^{2}·11·19 Posts 
GMP is an order quicker than Pari/GP for this task. I have attached my GMP code. Note that it misses out x^2x4, but it would take a minute to test this special case with Pari/GP.
I fixed that anomaly by using a repeatuntil construct instead of whiledo, and have uploaded the new code. Oops the edit was not functioning. Code reverted. Last fiddled with by paulunderwood on 20210623 at 21:08 
20210625, 12:39  #19  
Sep 2002
Database er0rr
2·3^{2}·11·19 Posts 
Quote:
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 20210625 at 12:50 

20210625, 21:25  #20 
Sep 2002
Database er0rr
EB2_{16} Posts 
I am slightly change the last test for practical purposes
Code:
{ tst(n,r)=local(t=lift(Mod(2,n)^r)); if(n==2n==3n==5,return(1)); if(gcd(30,n)!=1issquare(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)^(n1)==1&& Mod(Mod(x,n),x^2+(t^2/4+2)*x+1)^((n+1)/2)==kronecker(1,n); } EDIT: There are 2PSPs for which kronecker(t^2+16,n) are never equal to 1. Last fiddled with by paulunderwood on 20210626 at 20:33 
20210626, 20:32  #21 
Sep 2002
Database er0rr
3762_{10} Posts 
Fibonacci
Back to the drawing board...
Restrict n to 3 or 7 mod 20. Then x^(n+1) == b^2 (mod n, x^2b*xb^2) can be transformed into x^((n+1)/2) == 1 (mod n, x^2+3*x+1) and b^(n1) == 1 (mod n). I am now checking this out with gcd(b^61,n)==1. Here is code I am using; Code:
{ }for(n=1,100000000000, if((n%20==3n%20==7)&&!ispseudoprime(n)&&Mod(Mod(x,n),x^2+3*x+1)^((n+1)/2)==1, for(b=2,(n1)/2, if(Mod(b,n)^(n1)==1, print([n,b,gcd(b^61,n)]))))) } Last fiddled with by paulunderwood on 20210626 at 21:28 Reason: changed to gcd(b^61,n)==1 
20210627, 21:38  #22 
Sep 2002
Database er0rr
111010110010_{2} Posts 
Only x^22^r*x2
Just when I was about to give up on this thread I have a great test based on x^22^r*x2, which can be transformed into
Mod(2,n)^((n1)/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 2PSP list I see an amazing pattern: Code:
{ for(v=1,#V,n=V[v]; if(Mod(2,n)^((n1)/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]))))) } 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] 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 20210627 at 21:54 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Lucas and Fibonacci primes  Batalov  And now for something completely different  9  20170628 16:56 
Lucas Table  R.D. Silverman  Factoring  19  20120907 17:24 
Need help with Lucas Sequences...  WraithX  Programming  11  20100923 23:22 
LucasLehmer Test  storm5510  Math  22  20090924 22:32 
LucasLehmer  Dougal  Information & Answers  9  20090206 10:25 