Amazing 6

[paulunderwood]

Let f=x^2-2^r*x+b=0 with solutions 2*x = 2^r +- sqrt(4^r-4*b). Test Frobenius(2x) w.r.t. f and Euler-PRP(4^r-4*b) = -1 (all mod n), with the provisos kronecker(4^r -4*b,n)==-1 and gcd(4^r-2*b,n)==1 and gcd(4^r-b,n)==1 and not b|n.

The Forbenius test can be broken into a 2-PRP test and a Frobenius test on x.

Here is the test. For any non-square n find r and b:

• b%n!=0
• gcd(4^r-b,n)==1
• gcd(4^r-2*b,n)==1
• kronecker(4^r-4*b,n)==-1

and test:

• Mod(2,.n)^(n-1)==1
• Mod(4^r-4*b,n)^((n-1)/2)==-1
• Mod(Mod(1,n)*x,x^2-2^r*x+b)^(n+1)==b

Edit: I changed gcd(4^r-b^2,n) to gcd(4^r-b,n).

Edit2: I think gcd(4^r-b)==1 can be replaced by:
(gcd(b-1,n)==1&&gcd(4^r-1,n)==1)||(gcd(b+1,n)==1&&gcd(4^r+1,n)==1)

[paulunderwood]

Let x^2-a*x+b=0. The solutions are x=a/2 +- sqrt(a^2-4*b)/2.

The test is:

• b%n!=0
• !issquare(n)
• gcd(a^2-b,n)==1
• gcd(a^2-2*b,n)==1
• kronecker(a^2-4*b,n)==-1
• Mod(a^2/4-b,n)^((n-1)/2)==-1
• Mod(a/2,n)^(n-1)==1
• Mod(Mod(1,n)*x,x^2-a*x+b)^(n+1)==b

[paulunderwood]

To fool 2-PSPs and Carmichael numbers lists gcd(a^2-3*b,n)==1 is also required.

[paulunderwood]

I found some counterexamples to the above.

The revised test:

• b%n!=0
• !issquare(n)
• gcd(a^2-b,n)==1
• gcd(a^2-2*b,n)==1
• gcd(a^2-3*a,n)==1
• kronecker(a^2-4*b,n)==-1
• Mod(a^2/4-b,n)^((n-1)/2)==-1 //Euler PRP
• Mod(a/2,n)^((n-1)/2)==konecker(lift(Mod(a/2,n)),n) //Euler PRP
• Mod(Mod(1,n)*x,x^2-a*x+b)^(n+1)==b //Frobenius PRP

Further testing is ongoing.

A little bit of theory...

Let f = x^2-a*x+b=0 (which has roots x = a/2 +- sqrt(a^2-4*b)/2).

a = x+b/x mod f if kronecker(a^2-4*b,n)==-1.

a^2-2*b = x^2+b^2/x^2 mod f

(a^2-2*b)^2-2*b^2 = x^4+b^4/x^4 mod f

If gcd((a^2-2*b)^2-2*b^2,n)!=1 then d | R.H.S. and we can use Gaussian Elimination on the co-efficient of x and the term without x. This is complicated, but early calculations show that the GCDs given in the test above are sufficient and that there is no need to consider further recursions,

Here is a counterexample: [n,a,b]=[1894955311, 1756017110, 1]. Back to the drawing board; znlog(a,Mod(2,n)) == []

[paulunderwood]

[paulunderwood]

Recap: The solutions to x^2-2^r*x+b=0 are x=2^(r-1)+-sqrt(4^(r-1)-b).

Let r=1. Then the solutions are to the equation x^2-2*x+b=0 which are x=1+-sqrt(1-b)

We have to have kronecker(1-b,n)==-1, gcd(4-b,n)==1 and gcd(4-2*b,n)==1.

So no Fermat PRP test is needed; Just Frobenius+Euler.

I want to combine these into one test:

(x*(b-1))^((n+1)/2) == sqrt(b)*(b-1)*kronecker(X,n) (mod n, x^2-2*x+b)

where b is quadratic residue. But what is X?

[paulunderwood]

Apart form the ill-formed question, writing b=s^2 (and found by trial and error) the answer is:

(x*(1-s^2))^((n+1)/2) == s*(1-s^2)*kronecker(2*(1-s),n) (mod n, x^2-2*x+s^2),

Warning: this "fused" Euler and Frobenius test produces pseudoprimes. Testing to date has not found a counterexample when they are applied separately:

(1-b)^((n-1)/2 == -1 (mod n)
x^(n+1) == b (mod n, x^2-2*x+b)

where kronecker(1-b,n)==-1 and gcd(4-2*b,n)==1 and gcd(4-b,n)==1.

[paulunderwood]

[paulunderwood]

Here is a 1+1 selfridges algorithm:

Given a non-square n find b:

• kronecker(b,n)==1
• kronecker(1-b,n)==-1
• gcd(4-b,n)==1
• gcd(4-2*b,n)==1

and test

• Mod(b,n)^((n-1)/2)==1
• Mod(1-b,n)^((n-1)/2)==-1

I will try to explain my reasoning later.

Later reason: programming error The argument does not stack up. It was entirely based on the Euler test of post #74 and without the Frobenius part.

[paulunderwood]

[n,b] = [79786523, 2982537] is a counterexample to the test given in post #74 where r=1. This was overlooked because of the same programming error indicated in post #75. The only thing to be lifted from the ashes is that b is not minimal.

The cases where |b| =1 (post #71) have no counterexamples for n<5*10^12.

[paulunderwood]

The solutions to x^2-2*x-2^r=0 are 1 +- sqrt(1+2^r). This forms the basis of a test for non-square odd n:

• kronecker(1+2^r,n)==-1
• Mod(1+2^r,n)^((n-1)/2)==-1
• Mod(Mod(1,n)*x,x^2-2*x-2^r)^(n+1)==-2^r

I have tested the case r=0 against Feitsma's PSP-2 database (2^64) i.e. those for which kronecker(2,n)==-1.

Not having many free cycles at the moment, I have tested all r for n<10^5.
Edit: On further testing I found this anomoly:
[476971, Mod(476969, 476971)]. Henceforth I add the sub-test gcd(2^r+2,n)==1.
Edit 2: 2289717532901 passes Mod(-3,n)^((n-1)/2)==-1&&Mod(Mod(1,n)*x,x^2-2*x+4)^(n+1)==4.
Thus gcd(2^r+4,n)==1 is required.
My quest is now to find counterexamples for which 2^r != -2 nor -4 mod n.
Edit 3: [n,a]=[37870128451, 26812337209];gcd(a+2,n)
1403273.