20210628, 11:58  #23  
Sep 2002
Database er0rr
111011011111_{2} Posts 
Quote:
Code:
{ for(v=305962,#V,n=V[v]; if(Mod(2,n)^((n1)/2)==kronecker(2,n), z=znorder(Mod(2,n)); if(z%4==2, r=(z+2)/4;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), 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), g=gcd(t^2+2,n);print([v,n,g,z,r,t]))))))) } [305962, 14280816152219, 14280816152219, 90099218, 22524805, 2626041506362] [305962, 14280816152219, 11342983441, 90099218, 31047704, 6085369776326] [305962, 14280816152219, 14280816152219, 90099218, 67574414, 11654774645857] [305962, 14280816152219, 11342983441, 90099218, 76097313, 8195446375893] Last fiddled with by paulunderwood on 20210628 at 12:01 

20210628, 15:58  #24 
Sep 2002
Database er0rr
3^{4}·47 Posts 
Algorithm
Here is the algorithm for x^22^r*x2
Code:
{ tst(n)=local(t=2); \\ t=2^r if(n==2n==3,return(1)); \\ trivialiies if(n%2==0issquare(n)Mod(2,n)^((n1)/2)!=kronecker(2,n),return(0)); \\ even and newton and euler while(kronecker(t^2+8,n)!=1,t=t*2%n;if(t==1,return(0))); \\ seek strong kronecker. If none found assume composite gcd(t^2+2,n)==1&&Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(2,n); \\ euclid and lucas } Last fiddled with by paulunderwood on 20210628 at 16:19 
20210629, 01:55  #25 
Sep 2002
Database er0rr
EDF_{16} Posts 
For my blanket testing of all r, I notice those n that require a gcd are 5 mod 6. This will speed up a little of my search where "the pattern" holds.
Status: all 2PSPs < 3*10^10 and using "the pattern" < 5*10^13. It's time to move over to GMP, where I can employ a Lucas chain, plus some other optimizations. I also note that z=znorder(Mod(2,n)) is mostly small. "The pattern" is where the test with r=(z+2)/4 passes and requires gcd(t^2+2,n). Last fiddled with by paulunderwood on 20210629 at 02:20 
20210702, 01:44  #26  
Sep 2002
Database er0rr
111011011111_{2} Posts 
Quote:
I have now surpassed 9*10^11 for both quadratics x^2+(t^2/2+2)*x+1 and x^2+(t^2/4+2)*x+1 each with their incumbent Euler/Fermat PRP tests. This about winds up this thread. Last fiddled with by paulunderwood on 20210702 at 01:46 

20210706, 15:13  #27 
Sep 2002
Database er0rr
111011011111_{2} Posts 
Four Lucas Tests
Here my paper distilled from this thread

20210707, 19:40  #28 
Sep 2002
Database er0rr
3^{4}·47 Posts 
It occurred to me that since the tests involve t^2+something that only half of t might be used. For example:
Code:
{ tst(n)=local(t=2,k=kronecker(2,n),limit=2*log(n)*log(log(n)),l=0,nm1d2=(n1)/2); if(n==2n==3,return(1)); if(n%2==0issquare(n)Mod(2,n)^nm1d2!=k,return(0)); while(t>nm1d2kronecker(t^2+8,n)!=1,t=t*2%n;l++;if(t==1l>limit,return(0))); gcd(t^2+2,n)==1&&Mod(Mod(z,n),z^2+(t^2/2+2)*z+1)^((n+1)/2)==k; } Last fiddled with by paulunderwood on 20210707 at 19:44 
20210708, 03:01  #29 
Sep 2002
Database er0rr
111011011111_{2} Posts 
Revised paper
Here us the revised paper. I'll leave the original up for contrast,

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 