kronecker(2,n)==-1 test

[paulunderwood]

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:

{
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:

{
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

[paulunderwood]

{
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(a₁^2-a₂^2,n)>1

I have now found n with 3 or 4 solutions too, and gcd(a_i^2-a_j^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.

[CRGreathouse]

Originally Posted by paulunderwood

{
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.

[paulunderwood]

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:

{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.

[paulunderwood]

The rationale for the above test:

1. Matrix: [a,a;1,a]
2. Characteristic eqn: y^2-2*a+a^2-a==0
3. Solutions: y = a +- sqrt(a)
4. "Strong" transform: z^2-2*(a+1)/(a-1)*z+1=0 and Euler-(a^2-a)==-1
5. Solutions: z = (a+1)/(a-1) +- sqrt((a+1)^2/(a-1)^2 - 1) = (a+1)/(a-1) +- 2*sqrt(a)/(a-1)
6. Note1: if kronecker(a,n)==-1 and kronecker(a^2-a,n)==-1 then kronecker(a-1,n)==1
7. Note2: If a=-3 then z^2-z+1 = 0 => cyclotomic
8. Query1: Why is gcd(a^2+6*a+1,n)==1 needed?
9. Query2: is there a pseudoprime for this test?

{
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

[paulunderwood]

I am now testing:

{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.

[paulunderwood]

Latest test:

{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.

[paulunderwood]

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].