mersenneforum.org Divertimento
 Register FAQ Search Today's Posts Mark Forums Read

 2021-05-07, 10:24 #1 paulunderwood     Sep 2002 Database er0rr 1110011110012 Posts Divertimento 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 3×5×13×19 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 3·5·13·19 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 3×5×13×19 Posts fooled tst(10627*148793, 479362525) fools!
 2021-05-25, 05:47 #5 paulunderwood     Sep 2002 Database er0rr 3×5×13×19 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 3·5·13·19 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

3·5·13·19 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 71718 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

E7916 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 3·5·13·19 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 3×5×13×19 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