3 mod 4 with free parameter

[paulunderwood]

Consider [a,-1;1,a] = 2*a + [-a,-1;1,-a] where M=[a,-1;1,a] has the character x^2-2*a*x+a^2+1 and its discriminant = -1. Solving the character gives x=a+-sqrt(-1), leading to a test:

{tst(n,a)=n%4==3&&
gcd(a^3-a,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(a,n)^(n-1)==1&&
Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;}

Received wisdom says this test should have counterexamples. Puzzle: can you find one?

[paulunderwood]

Answer: [n, a]=[79786523, 1056446]

Now for a harder problem: Let a = 2^r, so that the test becomes:

{tst(n,r)=local(a=lift(Mod(2,n)^r));
n%4==3&&
gcd(a^3-a,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;}

[paulunderwood]

Originally Posted by paulunderwood

Now for a harder problem: Let a = 2^r, so that the test becomes:

{tst(n,r)=local(a=lift(Mod(2,n)^r));
n%4==3&&
gcd(a^3-a,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;}

Finding a counterexample to this looks hopeless. Before my computer crashed under the heat of the day, it had reached 4e11. I suspect a counterexample at maybe 25 digits or more. Very much more for r=1

[paulunderwood]

Originally Posted by paulunderwood

{tst(n,r)=local(a=lift(Mod(2,n)^r));
n%4==3&&
gcd(a^3-a,n)==1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1;}

Rather than computing gcd(a^3-a,n)==1 I think gcd(r,(n-1)/2)==1 is better. Certainly verification testing is quicker (both over znorder).

Note n divides 2^(n-1)-1.

gcd(a^2-1,n)==1 ==> gcd(2^(2*r)-1,2^(n-1)-1)==1 ==> gcd(2*r,n-1)==2 if gcd(r,(n-1)/2)==1.

Hence the required condition gcd(2,n-1)==2 which is met for n==3 mod 4.

[paulunderwood]

Let z=znorder(Mod(2,n)).

Then [2^(z-r),-1;1,2^(z-r)]^(n+1) == 4^(z-r)+1 == (4^z+4^r)/(4^r) == (1+4^r)/4^r all mod n

So 2^(r*(n+1))*[2^-r,-1;1,2^-r]^(n+1) = (1+4^r)*2^(r*(n-1)) mod n

Or [1,-2^r;2^r,1]^(n+1) == 4^r +1 == [2^r,-1;1,2^r]^(n+1) mod n

Hence I need only verify 0<r<(z+1)/2, Thus speeding up the verification program by a factor of two:

{for(v=1,#V,n=V[v];
if(n%4==3,z=znorder(Mod(2,n));print([v,n,z]);
for(r=1,(z+1)/2,
if(gcd(r,n-1)==1,a=lift(Mod(2,n)^r);
if(Mod(Mod(x+a,n),x^2+1)^(n+1)==a^2+1,
print([n,a,r,z]);break(2))))))}

where V is a list of base 2 pseudoprimes

Testing has reached 1.5e12

I have now added Mod(det,n)^((n-1)/2)==kronecker(det,n) where det=a^2+1, to speed it up some more.

Testing now at 2.7e12.

[paulunderwood]

Recap: I am testing: Fermat 2-prp and (x+2^r)^(n+1)==4^r+1 where gcd(r,n-1)==1, and have reached n<4*10^14 without counterexample.

Now, writing a=lift(Mod(2,n)^r) the Lucas part can be written as a Lucas test for y over y^2-2*a*y+a^2+1 which can be transformed into Euler-PRP for a^2+1 and z^((n+1)/2)==kronecker(a^2+1,n) (mod n, z^2-2*(a^2-1)/(a^2+1)*z+1).

In testing this I have found that a 2-PRP plus the Lucas test on z with gcd(a^2+1,n)==1 (and gcd(r,n-1)==1) is enough without the Euler test

[paulunderwood]

A small observation: If a number n==3 mod 4 is Fermat 2-PRP then 2^(n-1)==1 mod n. If z is the multiplicative order of 2 mod n, then z divides n-1. Also (x+2^z) == x+1 mod n. Furthermore, (x+1)^(n+1) == 2 (mod n, x^2+1) is equivalent to a Fermat 2-PRP test. Neat, eh? And gcd(r,n-1) implies gcd(r,z)==1.

[paulunderwood]

Originally Posted by paulunderwood

A small observation: If a number n==3 mod 4 is Fermat 2-PRP then 2^(n-1)==1 mod n. If z is the multiplicative order of 2 mod n, then z divides n-1. Also (x+2^z) == x+1 mod n. Furthermore, (x+1)^(n+1) == 2 (mod n, x^2+1) is equivalent to a Fermat 2-PRP test. Neat, eh? And gcd(r,n-1) implies gcd(r,z)==1.

On this theme, since n==3 mod 4 then n-1 is divisible by 2 and not 4. Then the only possible strengthening is a base 2 Euler PRP. That is up to multiplicative order, there seems to be one or two possible solutions for gcd(r,z)>1 to (x+2^r)^(n+1) == 4^r+1 (mod n, x^2+1).

Does anyone care to complete the proof of the test?

[paulunderwood]

Summarizing the two cases:

n%8=3 :: 2^((n-1)/2) == -1 mod n :: z/2 is odd :: two solutions exist: z and z/2
n%8=7 :: 2^((n-1)/2 == 1 mod n :: z is odd :: one solution exists.

Due to z being on average much smaller than n, what appears to be true might be the law of small numbers.The leap from Fermat 2-PRP plus (x+2^r)^(n+1) == 4^r+1 (mod n, x^2+1) with gcd(r,n-1) == 1 to only a test for (x+2)^(n+1) == 5 (mod n,x^2+1) is a large one. Is it better to push the testing boundary beyond my 2^50 limit for the latter or to try and prove Euler 2-PRP + the test for (x+2)?

[paulunderwood]

Originally Posted by paulunderwood

Summarizing the two cases:

n%8=3 :: 2^((n-1)/2) == -1 mod n :: z/2 is odd :: two solutions exist: z and z/2
n%8=7 :: 2^((n-1)/2 == 1 mod n :: z is odd :: one solution exists.

I forgot to add in an counting increment in my testing code. There are other cases.

I'll call it day after verification to 10^15 of the test:

n==3 mod 4
2^n==2 mod n
(I+2^r)^n==-I+2^r mod n where I is the sqrt(-1)
gcd(r,n-1)==1

[paulunderwood]

Originally Posted by paulunderwood

Recap: I am testing: Fermat 2-prp and (x+2^r)^(n+1)==4^r+1 where gcd(r,n-1)==1, and have reached n<4*10^14 without counterexample.

Now, writing a=lift(Mod(2,n)^r) the Lucas part can be written as a Lucas test for y over y^2-2*a*y+a^2+1 which can be transformed into Euler-PRP for a^2+1 and z^((n+1)/2)==kronecker(a^2+1,n) (mod n, z^2-2*(a^2-1)/(a^2+1)*z+1).

In testing this I have found that a 2-PRP plus the Lucas test on z with gcd(a^2+1,n)==1 (and gcd(r,n-1)==1) is enough without the Euler test

Taking the obvious case of r=1, then a Lucas test over y^2-4*y+5 can be transformed into a 5-Euler PRP test and a Euler-Lucas test over f(z)=z^2-6/5*z+1 (for gcd(5,n)==1). This has solutions of f(z)=0 for z=(3+-4*i)/5. The corresponding companion matrix is Z=[3/5,-4/5;1,0], the determinant of which is 4/5. Thus if n is base 2-Fermat PRP there is no need to do the base 5-Euler PRP test -- it is implied since det(Z)^k == det(Z^k) for all k.