Amazing 6

[paulunderwood]

The solutions to x^2-2*x-2^r=0 are 1 +- sqrt(1+2^r) and gives rise to the test:

• gcd(2^r+2,n)==1
• gcd(2^r+4,n)==1
• 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

Mod(Mod(1,n)*x,x^2-2*x-2^r)^(n+1)==-2^r implies Mod(-2^r,n)^(n-1)==1. If n was prime then Mod(2,n)^(n-1)==1. This greatly increases the scope for verification, e.g. using Feitsma's PSP-2 database.
Edit: This verification code uses this idea:

{forstep(n=3,1000000,2,if(!ispseudoprime(n),
z=znorder(Mod(2,n));for(r=1,z,if(r*(n-1)%z==0,
a=Mod(2,n)^r;if(kronecker(1+lift(a),n)==-1&&
Mod(1+a,n)^((n-1)/2)==-1&&Mod(Mod(1,n)*x,x^2-2*x-a)^(n+1)==-a,
print([n,a,gcd(a+2,n),gcd(a+4,n)]))))))}

[paulunderwood]

Originally Posted by paulunderwood

• gcd(2^r+2,n)==1
• gcd(2^r+4,n)==1
• 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

[n,a]=[1432999, 107552] is a counterexample.

[paulunderwood]

Flipping the sign or 2^r, I am now testing:

• gcd(2^r-2,n)==1
• gcd(2^r-4,n)==1
• 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

[paulunderwood]

If z is the multiplicative order of 2 mod n and kronecker(1-2^r,n)==-1 then gcd(2^z-1,2^r-1)==1 which implies gcd(r,z)==1. Hence z must divide n-1. Is that right?

We know z | eulerphi(n). Lehmer's totient conjecture is unproven. But can z | n-1?

The verification code is:

{forstep(n=3,1000000000,2,
if(!ispseudoprime(n),z=znorder(Mod(2,n));
if((n-1)%z==0,for(r=1,z,if(gcd(r,z)==1,a=Mod(2,n)^r;
if(kronecker(1-lift(a),n)==-1&&(1-a)^((n-1)/2)==-1&&
Mod(x,x^2-2*x+a)^(n+1)==a,
print([n,a,gcd(a-2,n),gcd(a-4,n)])))))))}

This is very fast

[paulunderwood]

Originally Posted by paulunderwood

If z is the multiplicative order of 2 mod n and kronecker(1-2^r,n)==-1 then gcd(2^z-1,2^r-1)==1 which implies gcd(r,z)==1. Hence z must divide n-1. Is that right?

We know z | eulerphi(n). Lehmer's totient conjecture is unproven. But can z | n-1?

Since z | n-1, 2^(n-1)==1 mod n. I can use a PSP-2 list. Without ispseudoprime() the verification code moves very quickly

[paulunderwood]

Apologies for writing sqrt(1-2^r) in two places where it should be just 1-2^r

It should read "Euler PRP test of 1-2^r" and "Jacobi symbol of 1-2^r over n"

Fixed.

There is a logical flaw in this paper. I cannot assume gcd(r,z)=1. The verification has reached only 4*10^6.

You can find a "flawless" replacement paper here,

[paulunderwood]

This latest test is looking good. I have run David Broadhurst's semiprime-CRT algorithm without finding a counterexample. I have also written a C+primesieve+Pari program -- I needed a good solution to znorder -- and it is very fast. What took nearly a week in pure Pari/GP (8.75E6) will take a few hours with this program. I will post an edit in this post to show how far the program has verified.

Final update: no pseudoprimes < 10^8

[paulunderwood]

I have attached the C/C++ code I am using to verify the above test.

I would appreciate any ideas for improvements that can be done. One idea is to have a threshold based on the size of z. If the order is small then it might be quicker to have functions based on "%" rather than my quick three_section_mod.

Note that the program needs the file Euler-Frobenius.dat containing something like

11 1000000000

BTW, I use primesive 4.4

Edit: I changed the code so there is one call to primesieve. Also masks are precomputed. I also introduced "threshold". The resulting code is 20% faster.

Edit2. Dropped unsigned int. Using global variables. More clean up and cosmetics.

Edit3. Polished version.

Remove ".c" extension to get the C++ file.

[paulunderwood]

In the previous I had x=1+-sqrt(1-2^r). I note that 2^r-1 (r>1) is never a square. So what else is never a square? In his proof of FLT case n=4 Fermat showed a^4+b^4 is never a square, which leads me onto the following test for odd non-square n:

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

The quadratic has solutions x=a^2+-sqrt(a^4+b^4) and so maybe I should be doing a base-a Fermat PRP test too. Anyway letting a=1 simplifies things greatly.

[paulunderwood]

I made a mistake: Case 4 of FLT uses the fact a^4-b^4 is never a square. So I have to flip the sign to get:

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

Letting a=1 simplifies the quadratic equation solution to x=1+-sqrt(1-b^4)

For a=1. the n that require GCDs are the same as those for the tests on x=1+-(1-2^r) except have more examples (for each n).

[paulunderwood]

Using Euler+Frobenius on x=1+-sqrt(1-b^4). For intermediate values s*x+t in left-right exponentiation of the Frobenius test we have:-

Squaring:

? Mod(s*x+t,x^2-2*x+b^4)^2
Mod((2*s^2 + 2*t*s)*x + (-b^4*s^2 + t^2), x^2 - 2*x + b^4)

Multiplying by the base x if the bit is 1:

? Mod(s*x+t,x^2-2*x+b^4)*x
Mod((2*s + t)*x - b^4*s, x^2 - 2*x + b^4)

Hence for small b squaring is 2 selfridges because all we need to calculate is 2*s*(s+t) and (t-b^2*s)*(t+b^2*s)



Edit: Counterexample to x=1+-sqrt(1-b^4):

? [n,b]=[2579*30937, 16641097];kronecker(1-b^4,n)==-1&&gcd(2-b^4,n)==1&&gcd(4-b^4,n)==1&&Mod(1-b^4,n)^((n-1)/2)==-1&&Mod(Mod(1,n)*x,x^2-2*x+b^4)^(n+1)==b^4
1