Thread: kronecker(2,n)==-1 test View Single Post
2021-02-18, 14:26   #15
paulunderwood

Sep 2002
Database er0rr

76058 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