Amazing 6

[paulunderwood]

Given non-square odd candidate prime n and b=6 and any r so that a=b^r, where kronecker(a^2-4,n)==-1 and gcd(a^3-a,n)==1. then the test

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

implies n is prime!

Proof? Counterexample? A strong test?

[Dr Sardonicus]

Originally Posted by paulunderwood

Given non-square odd candidate prime n and b=6 and any r so that a=b^r, where kronecker(a^2-4,n)==-1 and gcd(a^3-a,n)==1. then the test

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

implies n is prime!

Proof? Counterexample? A strong test?

Did you mean kronecker(b*(a+2),n)?

[paulunderwood]

Originally Posted by Dr Sardonicus

Did you mean kronecker(b*(a+2),n)?

Yes.

My testing with Pari/GP, using znorder(Mod(6,n)) in the script, has reached 3*10^10 without a counterexample,

[paulunderwood]

Since I stipulate that gcd(a^3-a,n)==1, I may as well say gcd(210,n)==1, since 6 divides a, 5 divides 6^r-1 for all r and 7 divides 6^r+1 for all r.

Testing has now reached 5*10^10

[CRGreathouse]

Would you post your script?

[paulunderwood]

Originally Posted by CRGreathouse

Would you post your script?

Sure. Here you go. It needs some enhancements and formatting :

b=6;forstep(n=1,10000000000000,2,if(n%10000000==1,print(">>"n));if(!ispseudoprime(n)&&!issquare(n)&&Mod(b,n)^(n-1)==1,z=znorder(Mod(b,n));for(r=0,z,a=lift(Mod(b,n)^r);if(gcd(a^3-a,n)==1&&kronecker(a^2-4,n)==-1&&Mod(Mod(1,n)*b*x,x^2-a*x+1)^((n+1)/2)==b*kronecker(b*(a+2),n),print([n,r,a])))))

[Dr Sardonicus]

Fascinating. Assuming this is a property possessed by all primes p satisfying the conditions, it implies that

if kronecker(a^2 - 4, p) = -1, then lift(Mod(x,x^2 - Mod(a,p)*x + 1)^((p+1)/2))) == kronecker(a+2, p).

I'm convinced that this is true, but I don't see why it's true. What is clear to me is, it's either kronecker(a+2,p) or kronecker(a-2, p). I'm probably overlooking something obvious...

[paulunderwood]

Originally Posted by Dr Sardonicus

Fascinating. Assuming this is a property possessed by all primes p satisfying the conditions, it implies that

if kronecker(a^2 - 4, p) = -1, then lift(Mod(x,x^2 - Mod(a,p)*x + 1)^((p+1)/2))) == kronecker(a+2, p).

I'm convinced that this is true, but I don't see why it's true. What is clear to me is, it's either kronecker(a+2,p) or kronecker(a-2, p). I'm probably overlooking something obvious...

Please see the beginning of section 6 of this

[Dr Sardonicus]

Originally Posted by paulunderwood

Please see the beginning of section 6 of this

Thanks! The wall was starting to buckle, and my head was beginning to hurt. Hmm... I guess it isn't completely obvious...

[paulunderwood]

Originally Posted by paulunderwood

Since I stipulate that gcd(a^3-a,n)==1, I may as well say gcd(210,n)==1, since 6 divides a, 5 divides 6^r-1 for all r and 7 divides 6^r+1 for all r.

Oops. 7 does not divide 6^r+1 for all r. However, 7 does divide 6^(2*r)-1 i.e. a^2-1 which divides a^3-a

[paulunderwood]

Testing has reached 2*10^11 with Pari/GP, having now switched over to the much quicker attached GMP script.