mod x^4+1

[paulunderwood]

Originally Posted by paulunderwood

Without checking Feitsma, we now have simple tests for n%8 = {3,5,7}

Transforming the test of x over x^2-136*x+16, I have now checked Feitsma's 2^64 PSP-2 list against:
(n%8==3||n%8==5)&&Mod(Mod(x,n),x^2-1154*x+1)^((n+1)/2)==1.

Given the test Mod(Mod(x+2),x^2+1)^(n+1)==5 seems to be good enough for n%4==3, then n%8==3 is covered by both tests. Which you choose depends on your needs and FFT arithmetic etc.

I am pleased with this advancement spurred on by the good doctor.

Similar antics for 3 mod 8 and 5 mod 8 can be done with x^2-20*x+2 with discriminant 2*2^2*3^2. Fietsma's list check out with Euler 2-PSPs against (n%8==3||n%8==5)&&Mod(Mod(x,n),x^2-198*x+1)^((n+1)/2)==kronecker(2,n).

[Dr Sardonicus]

I did come up with a "reduced" version of part of your condition Mod(Mod(1,n)+x,1+x^4)^n = Mod(1, n)*(1 - x) for n == 5 (mod 8)

First, when n == 5 (mod 8), lift(Mod(1 + x, 1 + x^4)^n) is a polynomial of degree less than 4, in which the coefficients of x^3 and x^2 are always equal, and the coefficients of x and 1 are always equal and opposite.

Let a_k be the coefficient of x in lift(Mod(1 + x, x^2 - 2)^k). This is a "Fibonacci-like" sequence: a₀ = 0, a₁ = 1, and a_k+2 = 2*a_k+1 + a_k.

Starting with a₁ we have 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, ...

When n == 5 (mod 8) the coefficients of x^3 and x^2 in lift(Mod(1 + x, 1 + x^4)^n) are divisible by n when n divides a_(n+1)/2.

Note that 5 divides a₃ = 5 and 13 divides a₇ = 169, but 21 does not divide a₁₁ = 5741.

I have not checked for composite n == 5 (mod 8) which fulfill this condition. (As you have noted, to satisfy your condition, n also has to be a base-2 pseudoprime.)

[paulunderwood]

I don't see why it has to be base 2 Fermat PRP; The norm is -1.

[Dr Sardonicus]

Originally Posted by paulunderwood

I don't see why it has to be base 2 Fermat PRP; The norm is -1.

By "your condition" I mean, any of Mod(Mod(1,n) + x, x^4 + 1)^n == Mod(1 + x^r, x^4 + 1) for n == r (mod 8), r =3, 5, or 7.

Any of these conditions imply that Mod(2,n)^n = Mod(2,n).

My "reduced" condition does NOT imply that Mod(2,n)^n = Mod(2,n) (see example next paragraph). It only covers part of the test for n == 5 (mod 8). It merely insures that in Mod(Mod(1,n) + x, x^4 + 1)^n, the coefficients of x^3 and x^2 are 0.

A mindless numerical sweep found that 1189 = 29*41 is not a 2-psp but does satisfy my "reduced" condition.

I note that 341, a 2-psp congruent to 5 (mod 8), does not satisfy my "reduced" condition.

So combining 2-psp with my "reduced" condition may work fairly well for n == 5 (mod 8), but I suspect there are 2-psp's congruent to 5 (mod 8) which satisfy my "reduced" condition, but not your condition

Mod(Mod(1,n) + x, x^4 + 1) = Mod(Mod(1,n) - x, x^4 + 1).

[Dr Sardonicus]

If n == 3 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(1,n)*x^3, x^4 + 1) coefficients of x and x^2 are 0

If n == 5 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(-1,n)*x, x^4 + 1) coefficients of x^2 and x^3 are 0

If n == 7 (mod 8) is prime, then Mod(Mod(1,n)+x,x^4 + 1)^n == Mod(Mod(1,n) + Mod(-1,n)*x^3, x^4 + 1) coefficients of x and x^2 are 0

The condition that any of these congruences hold (mod n) implies that Mod(2,n)^n == Mod(2,n).

Let lift(Mod(1+x, x^2 - 2)^k) = F[sub]k[sub]*x + L_k

The "reduced" partial conditions that the "wrong" coefficients of Mod(Mod(1,n)+x, x^4 + 1)^n are zero, are:

n == 3 (mod 8): n divides L_(n+1)/2

n == 5 (mod 8): n divides F_(n+1)/2

n == 7 (mod 8) n divides L_(n-1)/2

The "reductions" are possible because they are conditions of divisibility by n, and n is odd. This allows one to ignore minus signs and powers of 2 in the relevant coefficients.

The main part of getting rid of powers of 2 is to note that in the characteristic polynomial x^2 + 136*x + 16, substituting x = 4*x and dividing through by 16 gives x^2 + 34*x + 1.

It is then a simple matter to figure out the correct power of 2 in the coefficients, divide it out, and match up the (absolute values of) two consecutive of the resulting odd numbers to coefficients below.

Further substituting -x for x in x^2 + 34*x + 1 takes care of the minus signs, giving the polynomial x^2 - 34*x + 1. This is the characteristic polynomial of Mod(1+x, x^2 - 2)^4.

? for(i=1,20,f=lift(Mod(1+x,x^2-2)^i);print(i" "f))
1 x + 1
2 2*x + 3
3 5*x + 7
4 12*x + 17
5 29*x + 41
6 70*x + 99
7 169*x + 239
8 408*x + 577
9 985*x + 1393
10 2378*x + 3363
11 5741*x + 8119
12 13860*x + 19601
13 33461*x + 47321
14 80782*x + 114243
15 195025*x + 275807
16 470832*x + 665857
17 1136689*x + 1607521
18 2744210*x + 3880899
19 6625109*x + 9369319
20 15994428*x + 22619537

UPDATE: I figured out semi-reasonable formulations of the second partial conditions for n == 3, 5, and 7 (mod 8). In each case, the two conditions together are equivalent to your quartic condition.

I saw no way to eliminate the powers of 2 from the second partial conditions. The F and L sequences are as above.

I still cannot believe I figured out the second condition for n == 5 (mod 8). That one gave me fits!


n == 3 (mod 8)

n divides L_(n+1)/2 and (-1)^((n-3)/8) * 2^((n-3)/4) * L_(n-1)/2 == 1 (mod n)


n == 5 (mod 8)

n divides F_(n+1)/2 and (-1)^((n+3)/8) * 2^((n+3)/4) * F_(n-1)/4 * L_(n-1)/4 == 1 (mod n)

Note: Second condition can be restated as (-1)^((n+3)/8) * 2^((n-1)/4) * F_(n-1)/2 == 1 (mod n)


n == 7 (mod 8)

n divides L_(n-1)/2 and (-1)^((n+1)/8) * 2^((n-3)/4) * L_(n+1)/2 == 1 (mod n)