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

10001100010002 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 118816 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 23·3·11·17 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

23·3·11·17 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.

Last fiddled with by paulunderwood on 2021-07-02 at 01:46

2021-07-06, 15:13   #27
paulunderwood

Sep 2002
Database er0rr

23·3·11·17 Posts
Four Lucas Tests

Here my paper distilled from this thread
Attached Files
 Four_Lucas_Tests.pdf (42.8 KB, 98 views)

 2021-07-07, 19:40 #28 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 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

106108 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, 119 views)

2021-10-20, 02:59   #30
paulunderwood

Sep 2002
Database er0rr

23·3·11·17 Posts
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

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

Last fiddled with by paulunderwood on 2021-10-20 at 11:51

 2021-10-24, 08:25 #31 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 Posts 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
 2021-10-24, 15:38 #32 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 Posts 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
2021-10-26, 05:03   #33
paulunderwood

Sep 2002
Database er0rr

23×3×11×17 Posts
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
 prp_v2.c (2.5 KB, 51 views)

Last fiddled with by paulunderwood on 2021-10-28 at 21:57

 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 14:33.

Thu Feb 2 14:33:24 UTC 2023 up 168 days, 12:01, 1 user, load averages: 1.10, 1.12, 1.14