 mersenneforum.org Divertimento -- Four Lucas Tests
 Register FAQ Search Today's Posts Mark Forums Read  2021-05-07, 10:24 #1 paulunderwood   Sep 2002 Database er0rr 22·1,063 Posts Divertimento -- Four Lucas Tests Based on the Frobenius tests over: x^2-a*x+a==0 with kronecker(a^2-4*a,n)==-1 x^2-a*x-a==0 with kronecker(a^2+4*a,n)==-1 which can be transformed into a^((n-1)/2)==kronecker(a,n) (mod n) x^((n+1)/2)==kronecker(a,n) (mod n, x^2-(a-2)*x+1) x^((n+1)/2)==kronecker(-a,n) (mod n, x^2+(a+2)*x+1) I have tested up to n<10^6 with gcd(a^2-1,n)==1 without finding a counterexample pseudoprime. Last fiddled with by paulunderwood on 2021-05-15 at 04:09   2021-05-15, 04:04 #2 paulunderwood   Sep 2002 Database er0rr 22·1,063 Posts kronecker(a^2-4*a,n)==-1 kronecker(a^2+4*a,n)==-1 a^((n-1)/2)==kronecker(a,n) (mod n) x^((n+1)/2)==kronecker(a,n) (mod n, x^2-(a-2)*x+1) x^((n+1)/2)==kronecker(-a,n) (mod n, x^2+(a+2)*x+1) gcd(a^2-1,n)==1 Those n below 4*10^6 requiring gcd(a^2-1,n) are so few I can list them here: Code: [5777, 1854, 5777] [17261, 420, 421] [17261, 843, 421] [17261, 3790, 421] [17261, 5053, 421] [113573, 48910, 113573] [120581, 2942, 2941] [120581, 5881, 2941] [120581, 21453, 2941] [120581, 26468, 2941] [120581, 30276, 2941] [120581, 35291, 2941] [120581, 50863, 2941] [120581, 59686, 2941] [1033997, 317611, 1033997] [1729331, 422433, 13201] [1842581, 269647, 44941] [1842581, 449411, 44941] [1842581, 539291, 44941] [1842581, 584232, 44941] [3774377, 1256294, 3774377] [3900797, 1544479, 3900797] Last fiddled with by paulunderwood on 2021-05-15 at 04:15   2021-05-21, 14:16 #3 paulunderwood   Sep 2002 Database er0rr 22·1,063 Posts Let's turn the above into Pari/GP code: Code: { tst(n,a)= kronecker(a^2-4*a,n)==-1&& kronecker(a^2+4*a,n)==-1&& Mod(a,n)^((n-1)/2)==kronecker(a,n)&& Mod(Mod(x,n),x^2-(a-2)*x+1)^((n+1)/2)==kronecker(a,n)&& Mod(Mod(x,n),x^2+(a+2)*x+1)^((n+1)/2)==kronecker(-a,n); } In the example above, I did not trivially test tst(n,1). If I do test tst(n,1) and a gcd(a^2-1,n) is required I can loop over the rest of the a's (up to (n-1)/2 because of symmetry) and check for gcd(a^2-1,n). What I see for such a is that GCD(gcd(ai^2-1,n),gcd(aj^2-1,n)) is always greater than 1 (so far). Furthermore, all gcd(a^2-1,n) have so far been 1 mod 4. Last fiddled with by paulunderwood on 2021-05-21 at 15:45   2021-05-23, 13:35 #4 paulunderwood   Sep 2002 Database er0rr 10000100111002 Posts fooled tst(10627*148793, 479362525) fools!   2021-05-25, 05:47 #5 paulunderwood   Sep 2002 Database er0rr 102348 Posts New quest With my observations about GCDs, I now have a new quest to fool: Code: tstab(n,a,b)=tst(n,a)&&tst(n,b)&&gcd(a^2-b^2,n)==1;   2021-06-06, 10:53 #6 paulunderwood   Sep 2002 Database er0rr 22·1,063 Posts I have not yet found a counterexample to the previous test. I now propose a more general test: { tst(n,P,Q_i,Q_j)= kronecker(P^2-4*Q_i)==-1&& kronecker(P^2+4*Q_i)==-1&& kronecker(P^2-4*Q_j)==-1&& kronecker(P^2+4*Q_j)==-1&& Mod(Mod(x,n),x^-P*x+Q_i)^(n+1)==Q_i&& Mod(Mod(x,n),x^-P*x-Q_i)^(n+1)==-Q_i&& Mod(Mod(x,n),x^-P*x+Q_j)^(n+1)==Q_j&& Mod(Mod(x,n),x^-P*x-Q_j)^(n+1)==-Q_j&& gcd(Q_i^2-Q_j^2,n)==1; } or {tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;} {tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);} {tst4(n,P,Q_i,Q_j)=tst2(n,P,Q_i)&&tst2(n,P,Q_j)&&gcd(Q_i^2-Q_j^2,n)==1;} Last fiddled with by paulunderwood on 2021-06-06 at 12:33   2021-06-07, 07:35   #7
paulunderwood

Sep 2002
Database er0rr

22×1,063 Posts Quote:
 Originally Posted by paulunderwood I {tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;} {tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);} {tst4(n,P,Q_i,Q_j)=tst2(n,P,Q_i)&&tst2(n,P,Q_j)&&gcd(Q_i^2-Q_j^2,n)==1;}
tst4(9809, 577, 27, 171) fails, but if I add the remedy gcd(P,n)==1 all is good.

Last fiddled with by paulunderwood on 2021-06-07 at 08:10   2021-06-08, 00:13 #8 paulunderwood   Sep 2002 Database er0rr 10000100111002 Posts What is wrong with this argument? Let: x^2-P*x+Q=0 y^2-P*y-Q=0 s^2-P*s+R=0 t^2-P*t-R=0 Then: x^2+y^2-P*(x+y)=0 s^2+t^2-P*(s+t)=0 Or P=(x^2+y^2)/(x+y)=(s^2+t^2)/(s+t) That is since gcd(P,n)=1: (x^2+y^2)*(s+t)=(s^2+t^2)*(x+y) And the the following must be true since gcd(x^2+y^2, x+y) is either 1 or 2: x+y=s+t And so: x^2+y^2=(x+y)^2-2*x*y=s^2+t^2=(s+t)^2-2*s*t So that:x*y=s*t If a prime p divides x it must divide s or t Wlog then: x^2-P*x+Q==x^2-P*x+R I.e: p divides Q-R, but a condition is that gcd(Q^2-R^2,n)=1. QED   2021-06-10, 20:57   #9
paulunderwood

Sep 2002
Database er0rr

22·1,063 Posts Well that was a lot of BS maths.

Quote:
 Originally Posted by paulunderwood Let: x^2-P*x+Q=0 y^2-P*y-Q=0 s^2-P*s+R=0 t^2-P*t-R=0
I have tested (with strong kroneckers and gcd(P,n)==1 and gcd(Q^2-R^2,n)==1) for Q=1 up to n < 10^6 and for all Q for n up to 1.8*10^4 with Pari/GP. When I get some free time I will convert to my own C library Last fiddled with by paulunderwood on 2021-06-11 at 01:05   2021-06-11, 23:15 #10 paulunderwood   Sep 2002 Database er0rr 425210 Posts [n,P,Q,R]=[1162349, 2335, 1, 2234] fools tst4(). I have now revised the test; I insist that gcd(Q^2-1,n)==1 and gcd(R^2-1,n)==1 as well. Code: {tst1(n,P,Q)=kronecker(P^2-4*Q,n)==-1&&gcd(Q^2-1,n)==1&& Mod(Mod(x,n),x^-P*x+Q)^(n+1)==Q;} {tst2(n,P,Q)=tst1(n,P,Q)&&tst1(n,P,-Q);} {tst4(n,P,Q,Rj)=tst2(n,P,Q)&&tst2(n,P,R)&&gcd(Q^2-R^2,n)==1;}   2021-06-19, 08:02 #11 paulunderwood   Sep 2002 Database er0rr 22·1,063 Posts Restricted domain variation Here I test over x^2-x+2^r where kronecker(1-4*2^r,n)==-1 x^2-x-2^r where kronecker(1+4*2^r,n)==-1 If r is even this is the same as: 2^(n-1)==1 (mod n) x^((n+1)/2)==1 (mod n, x^2-(1/2^r-2)*x+1) x^((n+1)/2)==kronecker(-1,n) (mod n, x^2+(1/2^r+2)*x+1) if r is odd: 2^((n-1)/2)==kronecker(2,n) (mod n) x^((n+1)/2)==kronecker(2,n) (mod n, x^2-(1/2^r-2)*x+1) x^((n+1)/2)==kronecker(-2,n) (mod n, x^2+(1/2^r+2)*x+1) If r==0 we have: x^((n+1)/2)==kronecker(-1,n) (mod n, x^2+3*x+1) where kronecker(5,n)==-1 and kronecker(-3,n)==-1. and this has pseudoprimes: [5777, ... ] and consequently checking gcd(2^(2*r)-1,n)==1 is wise. To make the Lucas PRP tests more efficient we can instead calculate over x^2-x+-1/2^r and use small r. Last fiddled with by paulunderwood on 2021-06-19 at 23:33 Reason: Fixed the Lucas PRP tests expressions and exponents thereof. Plus, added pseudoprimes   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 19:11.

Sat Aug 13 19:11:42 UTC 2022 up 37 days, 13:59, 2 users, load averages: 1.48, 1.31, 1.15