 mersenneforum.org Divertimento -- Four Lucas Tests
 Register FAQ Search Today's Posts Mark Forums Read  2021-06-28, 11:58   #23
paulunderwood

Sep 2002
Database er0rr

1110110111112 Posts Quote:
 Originally Posted by paulunderwood 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]
Assuming z%4==2 and Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n) are necessary conditions, -- poof anyone? -- the next to break "the pattern" is

Code:
{
for(v=305962,#V,n=V[v];
if(Mod(-2,n)^((n-1)/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 2021-06-28 at 12:01   2021-06-28, 15:58 #24 paulunderwood   Sep 2002 Database er0rr 34·47 Posts Algorithm Here is the algorithm for x^2-2^r*x-2 Code: { tst(n)=local(t=2); \\ t=2^r if(n==2||n==3,return(1)); \\ trivialiies if(n%2==0||issquare(n)||Mod(-2,n)^((n-1)/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 2021-06-28 at 16:19   2021-06-29, 01:55 #25 paulunderwood   Sep 2002 Database er0rr EDF16 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 2-PSPs < 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 2021-06-29 at 02:20   2021-07-02, 01:44   #26
paulunderwood

Sep 2002
Database er0rr

1110110111112 Posts Quote:
 Originally Posted by paulunderwood "The pattern" is where the test with r=(z+2)/4 passes and requires gcd(t^2+2,n).
If r=(z+2)/4 then the quadratic x^2+(t^2/2+2)*x+1 is x^2+(2^((z+2)/2)/2+2)*x+1 is x^2+(2^(z/2)*2/2+2)*x+1. Since 2^(z/2)==-1 then the quadratic reduces to x^2+x+1 which is cyclotomic. A similar observation for r=3*(z+2)/4-1 can be had.

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 2021-07-02 at 01:46   2021-07-06, 15:13   #27
paulunderwood

Sep 2002
Database er0rr

1110110111112 Posts Four Lucas Tests

Here my paper distilled from this thread Attached Files Four_Lucas_Tests.pdf (42.8 KB, 23 views)   2021-07-07, 19:40 #28 paulunderwood   Sep 2002 Database er0rr 34·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=(n-1)/2); if(n==2||n==3,return(1)); if(n%2==0||issquare(n)||Mod(-2,n)^nm1d2!=k,return(0)); while(t>nm1d2||kronecker(t^2+8,n)!=-1,t=t*2%n;l++;if(t==1||l>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; } Note the introduction of "t>nm1d2". I'll update the paper later along with testing below 2*log(n)*log(log(log(n))) Last fiddled with by paulunderwood on 2021-07-07 at 19:44   2021-07-08, 03:01   #29
paulunderwood

Sep 2002
Database er0rr

1110110111112 Posts Revised paper

Here us the revised paper. I'll leave the original up for contrast,  Attached Files Four_Lucas_Tests.pdf (43.0 KB, 32 views)   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 9 2017-06-28 16:56 R.D. Silverman Factoring 19 2012-09-07 17:24 WraithX Programming 11 2010-09-23 23:22 storm5510 Math 22 2009-09-24 22:32 Dougal Information & Answers 9 2009-02-06 10:25

All times are UTC. The time now is 07:26.

Sun Sep 19 07:26:00 UTC 2021 up 58 days, 1:54, 0 users, load averages: 1.06, 1.15, 1.52