20210628, 11:58  #23  
Sep 2002
Database er0rr
7·23·29 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
7×23×29 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
7×23×29 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
7·23·29 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
7·23·29 Posts 
Four Lucas Tests
Here my paper distilled from this thread

20210707, 19:40  #28 
Sep 2002
Database er0rr
7×23×29 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
7×23×29 Posts 
Revised paper
Here us the revised paper. I'll leave the original up for contrast,

20211020, 02:59  #30 
Sep 2002
Database er0rr
11075_{8} 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. Last fiddled with by paulunderwood on 20211020 at 11:51 
20211024, 08:25  #31 
Sep 2002
Database er0rr
11075_{8} Posts 
A slight speed up
Rather than taking gcd(4^r4,n)==1 and gcd(4^r2,n)==1 the substitute gcd((r1)*(2*r1),n1)<=2 is quicker, resulting in the test:
Code:
{ tst(n,r)=local(k=kronecker(2,n);fr=lift(Mod(4,n)^r)); gcd((r1)*(2*r1),n1)<=2&& kronecker(fr8,n)==1&& Mod(2,n)^((n1)/2)==k&& Mod(Mod(x,n),x^2(fr/22)*x+1)^((n+1)/2)==k; } Last fiddled with by paulunderwood on 20211025 at 06:15 
20211024, 15:38  #32 
Sep 2002
Database er0rr
7×23×29 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((r1)*(2*r1),n1)<=2&& kronecker(fr8,n)==1&& Mod(Mod(2*x,n),x^2(fr/22)*x+1)^((n+1)/2)==2; } (s*x+t)^2 = s*(s*a+t*2)*x + (ts)*(t+s) (s*x+t)*(2*x) = (s*a+t)*2*x  s*2 where a=4^r/22. 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((r1)*(2*r1),n1)>2kronecker(4^r8,n)!=1,r++); a=2^(2*r1)2; for(b=2,LEN,temp=s*(s*a+t*2)%n;t=(ts)*(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 20211025 at 06:17 Reason: fixed typo in gcd 
20211026, 05:03  #33 
Sep 2002
Database er0rr
1001000111101_{2} Posts 
version for bash
The attached program returns exit(0) iff the input is 2Euler PRP and Lucas PRP. (It also uses gcd((r1)*(2*r1),n1)<=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^$i1)"  gp q  ./prp_v2; then echo "M$i Is 2Euler and Lucas PRP"; fi fi done */ 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 Last fiddled with by paulunderwood on 20211028 at 21:57 
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 