mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-06-28, 11:58   #23
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110110111112 Posts
Smile

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is online now   Reply With Quote
Old 2021-06-28, 15:58   #24
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

34·47 Posts
Default 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
paulunderwood is online now   Reply With Quote
Old 2021-06-29, 01:55   #25
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

EDF16 Posts
Default

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
paulunderwood is online now   Reply With Quote
Old 2021-07-02, 01:44   #26
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110110111112 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

"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
paulunderwood is online now   Reply With Quote
Old 2021-07-06, 15:13   #27
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110110111112 Posts
Default Four Lucas Tests

Here my paper distilled from this thread
Attached Files
File Type: pdf Four_Lucas_Tests.pdf (42.8 KB, 23 views)
paulunderwood is online now   Reply With Quote
Old 2021-07-07, 19:40   #28
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

34·47 Posts
Default

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
paulunderwood is online now   Reply With Quote
Old 2021-07-08, 03:01   #29
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110110111112 Posts
Default Revised paper

Here us the revised paper. I'll leave the original up for contrast,
Attached Files
File Type: pdf Four_Lucas_Tests.pdf (43.0 KB, 32 views)
paulunderwood is online now   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 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

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.