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

75368 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 offline   Reply With Quote
Old 2021-06-28, 15:58   #24
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 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 offline   Reply With Quote
Old 2021-06-29, 01:55   #25
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

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

2·7·281 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 offline   Reply With Quote
Old 2021-07-06, 15:13   #27
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default Four Lucas Tests

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

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

2·7·281 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, 61 views)
paulunderwood is offline   Reply With Quote
Old 2021-10-20, 02:59   #30
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default GMP code for test #3

I have coded up test #3 from the above paper.

Code:
// gcc -o prp prp.c -lgmp
// usages:-
// ./prp
// ./prp <integer>
// echo "print(<expression>)" | gp -q | ./prp
Edit: Added comments, an else, GCDs and more meaningful variable names.

BTW all 3 tests have been verified for all case below 2.5<10^13.
Attached Files
File Type: c prp.c (2.5 KB, 14 views)

Last fiddled with by paulunderwood on 2021-10-20 at 11:51
paulunderwood is offline   Reply With Quote
Old 2021-10-24, 08:25   #31
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2·7·281 Posts
Default A slight speed up

Rather than taking gcd(4^r-4,n)==1 and gcd(4^r-2,n)==1 the substitute gcd((r-1)*(2*r-1),n-1)<=2 is quicker, resulting in the test:

Code:
{
tst(n,r)=local(k=kronecker(2,n);fr=lift(Mod(4,n)^r));
gcd((r-1)*(2*r-1),n-1)<=2&&
kronecker(fr-8,n)==-1&&
Mod(2,n)^((n-1)/2)==k&&
Mod(Mod(x,n),x^2-(fr/2-2)*x+1)^((n+1)/2)==k;
}
Although I titled this post "speed up", the real effect is to reduce the domain.

Last fiddled with by paulunderwood on 2021-10-25 at 06:15
paulunderwood is offline   Reply With Quote
Old 2021-10-24, 15:38   #32
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

393410 Posts
Default 2 selfidge version

We can fuse the Euler and Lucas test thusly:

Code:
{
tst(n,r)=local(fr=lift(Mod(4,n)^r));
gcd((r-1)*(2*r-1),n-1)<=2&&
kronecker(fr-8,n)==-1&&
Mod(Mod(2*x,n),x^2-(fr/2-2)*x+1)^((n+1)/2)==2;
}
To see it is 2 selfridges note that for binary exponentiation intermediate values:

(s*x+t)^2 = s*(s*a+t*2)*x + (t-s)*(t+s)
(s*x+t)*(2*x) = (s*a+t)*2*x - s*2

where a=4^r/2-2.

So the algorithm would be:

Code:
{
tst(n)=local(r=2,s=2,t=0,BIN=binary(n+1),LEN=length(BIN)-1,a,b,temp);
if(n==2,return(1));if(n%2==0,return(0));
if(issquare(n),return(0));
while(gcd((r-1)*(2*r-1),n-1)>2||kronecker(4^r-8,n)!=-1,r++);
a=2^(2*r-1)-2;
for(b=2,LEN,temp=s*(s*a+t*2)%n;t=(t-s)*(t+s)%n;s=temp;
 if(BIN[b],temp=(s*a+t)*2%n;t=-s*2%n;s=temp));
if(s==0&&t==2,return(1));0;
}

Last fiddled with by paulunderwood on 2021-10-25 at 06:17 Reason: fixed typo in gcd
paulunderwood is offline   Reply With Quote
Old 2021-10-26, 05:03   #33
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×7×281 Posts
Default version for bash

The attached program returns exit(0) iff the input is 2-Euler PRP and Lucas PRP. (It also uses gcd((r-1)*(2*r-1),n-1)<=2.)

Code:
// gcc -o prp_v2 prp_v2.c -lgmp
// bash use case:-
/*
for i in {1..2281}; do 
    if ./prp_v2 $i; then 
        if echo "print(2^$i-1)" | gp -q | ./prp_v2; then
            echo "M$i Is 2-Euler and Lucas PRP";
        fi
    fi
done
*/
Edit: latest code has a little trial division to speed up testing.

Edit2: fixed the trial division (albeit not very good) where "r" in the loop got clobbered and so was meaningless on finishing the loop. Now "r" remains intact and I use "d" instead in the loop
Attached Files
File Type: c prp_v2.c (2.5 KB, 8 views)

Last fiddled with by paulunderwood on 2021-10-28 at 21:57
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 16:15.


Tue Nov 30 16:15:32 UTC 2021 up 130 days, 10:44, 0 users, load averages: 1.40, 1.38, 1.41

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.