mersenneforum.org kronecker(2,n)==-1 test
 Register FAQ Search Today's Posts Mark Forums Read

2021-02-16, 03:26   #12
paulunderwood

Sep 2002
Database er0rr

381410 Posts

Quote:
 Originally Posted by paulunderwood Consider respectively the matrices [1,a;1,1] and [1,1-a;1,1] whose characteristic equations are: y^2-2*y+1-a=0 y^2-2*y+a=0 with solutions: y=1+-sqrt(a) y=1+-sqrt(1-a) Restrict to kronecker(a,n)==-1 and kronecker(1-a,n)==-1 Now transform the characteristic equations (ignoring Euler "Q"-PRP tests) to z^2-(4/(1-a)-2)*z+1=0 z^2-(4/a-2)*z+1=0 With a Fermat base 2 PRP test I propose: Code: { tst(n,a)=Mod(2,n)^(n-1)==1&& kronecker(a,n)==-1&& kronecker(1-a,n)==-1&& Mod(Mod(z,n),z^2-(4/(1-a)-2)*z+1)^((n+1)/2)==-1&& Mod(Mod(z,n),z^2-(4/a-2)*z+1)^((n+1)/2)==-1; }
Doing the same mathematics with matrices [b,a;1,b] and [b,b^2-a;1,b] leads to a test which is not producing counterexamples:

Code:
{
tst(n,a,b)=local(Q=b^2-a);
kronecker(a,n)==-1&&
kronecker(Q,n)==-1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(z,n),z^2-(4*b^2/Q-2)*z+1)^((n+1)/2)==-1&&
Mod(Mod(z,n),z^2-(4*b^2/a-2)*z+1)^((n+1)/2)==-1;
}
Furthermore, when a=b=2 then b^2-a=2 which cuts the test down to a Fermat 2-PRP test and a strong Lucas test over z^2-6*z+1

Last fiddled with by paulunderwood on 2021-02-16 at 04:13

 2021-02-18, 02:33 #13 paulunderwood     Sep 2002 Database er0rr 381410 Posts Unique solution test Code: { tst(n,a)=local(A=a^2+a); kronecker(A,n)==-1&& kronecker(a,n)==-1&& Mod(A,n)^((n-1)/2)==-1&& Mod(a,n)^((n-1)/2)==-1&& Mod(Mod(z,n),z^2-(4*a/(a-1)-2)*z+1)^((n+1)/2)==-1 } I am running this test against Richard Pinch's Carmichael number list and with David Broadhurst's CRT Semi-prime Pari/GP script. The latter has only produced unique solutions for a given n, making 2 rounds with different a's sufficient for a primality proof?!?!? Those pesky primes! I just found 2 solutions for 2728624939. However gcd(a1^2-a2^2,n)>1 I have now found n with 3 or 4 solutions too, and gcd(ai^2-aj^2,n)>1 for i != j. I am seeing the same sort of GCDs for A=a+1 and kronecker(A,n)==-1. Hence the corresponding test can be done for suitable {a, a+1} and {a+1,a+2} which reduces the number of sub-tests, and no GCD need be calculated. Last fiddled with by paulunderwood on 2021-02-18 at 05:03
2021-02-18, 13:51   #14
CRGreathouse

Aug 2006

175B16 Posts

Quote:
 Originally Posted by paulunderwood Code: { tst(n,a)=local(A=a^2+a); kronecker(A,n)==-1&& kronecker(a,n)==-1&& Mod(A,n)^((n-1)/2)==-1&& Mod(a,n)^((n-1)/2)==-1&& Mod(Mod(z,n),z^2-(4*a/(a-1)-2)*z+1)^((n+1)/2)==-1 } I am running this test against Richard Pinch's Carmichael number list and with David Broadhurst's CRT Semi-prime Pari/GP script.
Given a Carmichael number N or a semiprime p*q, what code do you run against it, exactly? Surely you're not looping over possible a, that would take forever.

2021-02-18, 14:26   #15
paulunderwood

Sep 2002
Database er0rr

2×1,907 Posts

Quote:
 Originally Posted by CRGreathouse Given a Carmichael number N or a semiprime p*q, what code do you run against it, exactly? Surely you're not looping over possible a, that would take forever.
I found a counterexample to the above test for n=137975195359.

I am now testing:

Code:
{tst(n,a)=kronecker(a,n)==-1&&kronecker(a-1,n)==1&&kronecker(a+1,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&Mod(a-1,n)^((n-1)/2)==1&&Mod(a+1,n)^((n-1)/2)==-1&&
Mod(Mod(x,n),x^2-(4*a/(a-1)-2)*x+1)^((n+1)/2)==-1;}

{tst1(p,q)=local(n=p*q,u=[]);
for(a=2,p-3,if((n%(p-1)==1)||
Mod(a,p)^(n-1)==1&&Mod(a-1,p)^(n-1)==1&&Mod(a+1,p)^(n-1)==1&&
Mod(Mod(x,p),x^2-(4*a/(a-1)-2)*x+1)^(n+1)==1,
u=concat(u,a)));Mod(u,p);}

{tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
if(#V,for(v=1,#V,print([n,V[v],gcd(V[v]^2-V[1]^2,n)])));V;}

{forprime(p=7,10000000,for(k=4,12,q=1+2*k*(p-1);
if(ispseudoprime(q),tst2(p,q))));
print("\\\\ "round(gettime/1000)" seconds");}
(For Carmichael I do loop over a and yes it is too slow to run.)

This test has zero or a unique solution for n so far; These unique solutions have either a+3==n or a+1/a+6 == 0 mod n.

I found a non-unique solution. So I have added justifiable Fermat 2-PRP into the test and am running again.

Last fiddled with by paulunderwood on 2021-02-19 at 06:05 Reason: FIXED JACOBI SYMBOL

 2021-02-19, 10:41 #16 paulunderwood     Sep 2002 Database er0rr 2·1,907 Posts Rationale The rationale for the above test: Matrix: [a,a;1,a] Characteristic eqn: y^2-2*a+a^2-a==0 Solutions: y = a +- sqrt(a) "Strong" transform: z^2-2*(a+1)/(a-1)*z+1=0 and Euler-(a^2-a)==-1 Solutions: z = (a+1)/(a-1) +- sqrt((a+1)^2/(a-1)^2 - 1) = (a+1)/(a-1) +- 2*sqrt(a)/(a-1) Note1: if kronecker(a,n)==-1 and kronecker(a^2-a,n)==-1 then kronecker(a-1,n)==1 Note2: If a=-3 then z^2-z+1 = 0 => cyclotomic Query1: Why is gcd(a^2+6*a+1,n)==1 needed? Query2: is there a pseudoprime for this test? Code: { tst(n,a)= gcd(a+3,n)==1&& gcd(a^2+6*a+1,n)==1&& kronecker(a,n)==-1&& kronecker(a-1,n)==1&& kronecker(a+1,n)==-1&& Mod(2,n)^(n-1)==1&& Mod(a,n)^((n-1)/2)==-1&& Mod(a-1,n)^((n-1)/2)==1&& Mod(a+1,n)^((n-1)/2)==-1&& Mod(Mod(z,n),z^2-(4*a/(a-1)-2)*z+1)^((n+1)/2)==-1; } I found 4 counterexamples for n = 6192880203469 Last fiddled with by paulunderwood on 2021-02-21 at 05:49 Reason: wrong n
 2021-02-21, 05:21 #17 paulunderwood     Sep 2002 Database er0rr EE616 Posts All Euler-PRP = -1 I am now testing: Code: {tst(n,a)=kronecker(a,n)==-1&&kronecker(a-1,n)==-1&&kronecker(a+1,n)==-1&& Mod(a,n)^((n-1)/2)==-1&&Mod(a-1,n)^((n-1)/2)==-1&&Mod(a+1,n)^((n-1)/2)==-1&& Mod(Mod(x,n),x^2-(4*a/(a-1)-2)*x+1)^((n+1)/2)==1;} {tst1(p,q)=local(n=p*q,u=[]); for(a=2,p-2,if((n%(p-1)==1)|| Mod(a,p)^(n-1)==1&&Mod(a-1,p)^(n-1)==1&&Mod(a+1,p)^(n-1)==1&& Mod(Mod(x,p),x^2-(4*a/(a-1)-2)*x+1)^(n+1)==1, u=concat(u,a)));Mod(u,p);} {tst2(p,q)=local(n=p*q,up,uq,a,V=[]); up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq, for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j])); if(tst(n,a),V=concat(V,a))))));V=vecsort(V); if(#V,for(v=1,#V,print([n,V[v],gcd(V[v]+3,n),gcd(3*V[v]+1,n),gcd(V[v]^2+6*V[v]+1,n)])));V;} {forprime(p=7,1000000,for(k=4,12,q=1+2*k*(p-1); if(ispseudoprime(q)&&Mod(2,p*q)^(p*q)==2,tst2(p,q)))); print("\\\\ "round(gettime/1000)" seconds");} This takes about 90 hours. I found a counterexample for n=415681338623. Now I am testing with a 3-PRP test too since "3" is in the GCDs. Last fiddled with by paulunderwood on 2021-02-21 at 14:58
 2021-02-21, 16:17 #18 paulunderwood     Sep 2002 Database er0rr 1110111001102 Posts Latest test: Code: {EulerPRP(a,n)=Mod(a,n)^((n-1)/2)==kronecker(a,n);} { tst(n,a)= gcd(a+3,n)==1&& gcd(3*a+1,n)==1&& gcd(a^2+6*a+1,n)==1&& kronecker(a,n)==-1&& Mod(a,n)^((n-1)/2)==-1&& EulerPRP(2,n)&& EulerPRP(3,n)&& EulerPRP(a-1,n)&& EulerPRP(a+1,n)&& Mod(Mod(x,n),x^2-(4*a/(a-1)-2)*x+1)^((n+1)/2)==kronecker(a*(a-1),n); } If this fails I will have hit a brick wall. Last fiddled with by paulunderwood on 2021-02-21 at 16:33
 2021-02-21, 18:57 #19 paulunderwood     Sep 2002 Database er0rr EE616 Posts Big question Are the solutions to b^2 = 2^i*3^j + 1 finite? (i, j >= 0) I have only found b in [2, 3, 5 ,7, 17]. Last fiddled with by paulunderwood on 2021-02-21 at 19:38

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 Trilo Miscellaneous Math 25 2018-03-11 23:20 lidocorc Software 3 2008-12-03 15:12 swinster Software 2 2007-12-01 17:54 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 06:06.

Wed Sep 22 06:06:20 UTC 2021 up 61 days, 35 mins, 0 users, load averages: 1.42, 1.46, 1.39