kronecker(2,n)==-1 test

[paulunderwood]

All is quiet from this run:

{
forstep(n=9,100000000,2,
if(!ispseudoprime(n)&&kronecker(2,n)==-1&&
Mod(Mod(x+2,n),x^2-2)^n==-x+2,
print([n])))
}

I can't generalize it without breaking it.

[paulunderwood]

Since for the above test I am working mod x^2-2 the value of x can be taken to be sqrt(2) The base is (x+2) or sqrt(2)*(1+x). So I ran to n<2^64 using Feitsma's PSP list with the following program:

{
for(v=1,#V,n=V[v];
if(kronecker(2,n)==-1&&
Mod(Mod(x+1,n),x^2-2)^n==-x+1,
print([n])))
}

All quiet!

[paulunderwood]

The general test is:

{
tst(a,n)=
kronecker(a,n)==-1&&Mod(a,n)^((n-1)/2)==-1&&
Mod(Mod(x+1,n),x^2-a)^n==-x+1
}

I should have known. A counterexample [n,a]=[54029741, 36019827].

If a minimal "a" is used then things might work out, maybe less than the square root of n?

[paulunderwood]

I have tested for a<sqrt(n) all Carmichael numbers < 10^14.

Test recap for non-square odd n:

• a<sqrt(n)
• Jacobi(a,n)==-1
• a^((n-1)/2)==-1 (mod n)
• (x+1)^n==-x+1 (mod n, x^2-a)

Note: by way of the binomial theorem and Frobenius automorphism, for prime n:

x^n+1 = -x + 1 (mod n, x^2-a)

=> x^(n-1) = -1 (mod n, x^2-a)

=> a^((n-1)/2) = -1 mod n

[paulunderwood]

For n==5 mod 8 it seems that testing Mod(Mod(x+1,n),x^2+2)^n==-x+1 is sufficient.

[paulunderwood]

Originally Posted by paulunderwood

• a<sqrt(n)
• Jacobi(a,n)==-1
• a^((n-1)/2)==-1 (mod n)
• (x+1)^n==-x+1 (mod n, x^2-a)

I have tested:

• Carmichael numbers up to 10^14 with Pari/GP
• semiprimes with David Broadhurst's CRT Pari/GP script -- 1 hour run
• now with C+PrimeSieve all applicable "a" for all n < 2.6*10^8 and counting.

[paulunderwood]

in coding up the above test, I realized that it is 1+3 selfridges -- where a selfridge is the time taken to do a fermat-PRP test. In section 2.5 "Implemenation of the test" [1] they seem to implement it very efficiently. I need to read their paper again to get 1+2 selfridges.

Also x+1 is equivalent to [1,a;1,1] whose determinant is 1-a: An implicit 1-a PRP test is done. A bonus!

[1] An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates

Edit: having read that section I can see that squaring for intermediate value s*x+t during left-right exponentiation is given by

[s,t] = [2*s*t, (a*s+t)*(s+t)-(a+1)*s*t]

Multiplying by the base x+1 is simply:

[s,t] = [s+t, a*s+t]

[paulunderwood]

Taking powers of x+1 (mod n, x^2-a) is the same as taking powers of M:=[1,a;1,1] mod n. The characteristic equation of M is y^2-2*y+1-a=0 whose solutions are y=1 +- sqrt(a). So we can take a Frobenius test of y over (y-1)^2-a, trivially a Fermat -1-PRP test and an Euler-PRP test for base a. Since we know y=1+-x, this Frobenius test is the same as doing it for x+1 over x^2-a.

Why do I require that a<sqrt(n)? I cannot answer this. I know x^2-a == 0 mod n but cannot make further progress.

[paulunderwood]

Powers of x+a+1 (mod n, x^2-a) is the same as powers of [a+1,a;1,a+1] mod n. The characteristic equation of this matrix is:
y^2-2*(a+1)*y+(a+1)^2-a=0 whose solution is y=(a+1)+-sqrt(a). Doing the old Frobenius-Fermat-Euler trick gives the following test:

{
tst(n,a)=
kronecker(a,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(a+1,n)^n==a+1&&
Mod(Mod(x+a+1,n),x^2-a)^n==-x+a+1
}

Note there is an implicit Fermat a^2+a+1 PRP test from the determinant.

In fact the Frobenius test over y^2-P*y+Q can be transformed into one over z^2-(P^2/Q-2)*z+1 and a base a^2+a+1 Euler PRP test:

{
tst2(n,a)=local(Q=a^2+a+1);
kronecker(a,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(a+1,n)^(n-1)==1&&
Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
Mod(Mod(z,n),z^2-(2*a^2+6*a+2)/Q*z+1)^((n+1)/2)==kronecker(Q,n)
}

So two Euler, one Fermat and one Lucas PRP tests. (1+1+1+2 selfridges.)

Unless I made a programming error, no counterexamples so far...

Here is one: [n,a]=[32626447351, 2108403400]. The remedy is to add gcd(X,n)==1 where X=2*a^2+6*a+2.

Here is one that I can't dodge: [n,a] = [27536216921, 3753815259]

[paulunderwood]

Without much ado, I am testing:

{
tst(n,a)=local(Q=1-a);
kronecker(a,n)==-1&&
kronecker(Q,n)==-1&&
gcd(a+3,n)==1&&
gcd(3*a+1,n)==1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(Q,n)^((n-1)/2)==-1&&
Mod(Mod(z,n),z^2-(4/Q-2)*z+1)^((n+1)/2)==-1;
}

I claim 3 rounds are enough with a₀, a₁ and a₂, checking gcd(a_i^2 - a_j^2,n)>1 for some combination.

[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;
}