mod x^4+1

[Dr Sardonicus]

Originally Posted by paulunderwood

I did say "any k". Powers k never seem to map x+1 to 1-x. HTH.

So you did. I just read "n" all the way through. Oops.

No good ideas for this question, either. At least not yet. I'm pretty sure I know how to get closed formulas for the coefficients of (1+x)^k (mod x^4 + 1), but I'm not sure they'd help much with the question at hand.

[paulunderwood]

The companion matrix of x^4+1 is:

? cm=([0,0,0,-1;1,0,0,0;0,1,0,0;0,0,1,0])
                                                   
[0 0 0 -1]                                         
[1 0 0  0]                                         
[0 1 0  0]                                         
[0 0 1  0]

Then x+1 is equivalent to:

? cm+1                                     
                                                   
[1 0 0 -1]                                         
[1 1 0  0]                                         
[0 1 1  0]                                         
[0 0 1  1]

The determinant of this matrix is 2:

? matdet(cm+1)                                     
2

So is it safe to say a test of PRP test of x+1 over x^4+1 is necessarily a 2-PRP?

Answer: Yes, according to https://en.wikipedia.org/wiki/Determ..._matrix_groups

This makes verification to 2^64 easy. I/4 of odd n for n%8==5 and 8 Selfridges per test...

Verified to 2^64 using Feitsma's list of 2-PSPs.

[Dr Sardonicus]

Originally Posted by paulunderwood

So is it safe to say a test of PRP test of x+1 over x^4+1 is necessarily a 2-PRP?

Quite safe. Here's another way to look at this:

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

taking the norm gives (Mod(2, n))^n = 2.

Verified to 2^64 using Feitsma's list of 2-PSPs.

Well done, Sir!

[paulunderwood]

FWIW, not a peep out of:

{forstep(n=5,1000000,8,
  if(!ispseudoprime(n),
    for(a=1,(n-1)/2,
      if(gcd(a,n)==1,
        Det=Mod(a,n)^4+1;
        if(Det^n==Det&&Mod(Mod(x+a,n),x^4+1)^n==a-x,
          print([n,a]))))));}

[Dr Sardonicus]

Originally Posted by paulunderwood

You may be aware that no one has found a counterexample to the test Mod(Mod(x+2,n),x^2+1)^(n+1)==5 for n%4==3.
<snip>

BTW, similar to your observation with Mod(Mod(1,n)*x + 1, x^4 + 1),

Mod(Mod(1,n)*x + 2, x^2 + 1)^(n+1) == 5 implies 5^(n-1) == 1 (mod n) for n == 3 (mod 4) (assuming 5 does not divide n). That is, n is a Fermat pseudoprime to the base 5. I do not know if these have been as extensively computed as Fermat pseudoprimes to the base 2.

But my guess is, even if they haven't been, if you run the base 5 test first, and only run Mod(Mod(x+2,n),x^2+1)^(n+1)==5 on the composite survivors, that will speed things up.

[paulunderwood]

Originally Posted by Dr Sardonicus

BTW, similar to your observation with Mod(Mod(1,n)*x + 1, x^4 + 1),

Mod(Mod(1,n)*x + 2, x^2 + 1)^(n+1) == 5 implies 5^(n-1) == 1 (mod n) for n == 3 (mod 4) (assuming 5 does not divide n). That is, n is a Fermat pseudoprime to the base 5. I do not know if these have been as extensively computed as Fermat pseudoprimes to the base 2.

But my guess is, even if they haven't been, if you run the base 5 test first, and only run Mod(Mod(x+2,n),x^2+1)^(n+1)==5 on the composite survivors, that will speed things up.

Computing 5-PSPs up to 2^64 would be a mammoth task involving many dedicated years of running efficient code on big hardware. I think getting the list of 2-PSPs involved some mathematical tricks that I do not understand. All I can offer beyond my 2^50 check is a scan of Feitsma's sub-list of Carmichael numbers, which I just check up to 2^64 in less than a second, not counting the time to read the list into memory.

[Dr Sardonicus]

Let

v=[Mod(1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2), Mod(-1/4*x^3 + 3/4*x^2 - 3/4*x + 1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2), Mod(-1/4*x^2 + 1/2*x - 1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2), Mod(-1/4*x + 1/4, x^4 - 4*x^3 + 6*x^2 - 4*x + 2)];

Then for k = 0, 3 the coefficient of x^k in lift(Mod(1+x, 1+x^4)^n) is trace(v[k+1]*x^n).

The only really "nice" expression is for the constant term, trace(Mod(1/4,x^4 - 4*x^3 + 6*x^2 - 4*x + 2)*x^n). This may be expressed as

The coefficients all grow exponentially with n, with the ratio of consecutive terms approaching sqrt((2 + sqrt(2))).

Scratch that. The polynomial has two (complex conjugate) zeroes of absolute value sqrt(2 + sqrt(2)) and two of absolute value sqrt(2 - sqrt(2)). The expression is zero for n == 4 (mod 8).

What is true is that the n-th root of the absolute value of the n-th constant term has an upper limit of sqrt(2 + sqrt(2)).


Note: The polynomial x^4 - 4*x^3 + 6*x^2 - 4*x + 2 is charpoly(Mod(x+1,x^4 + 1)).

I wasn't advocating compiling a table of base-5 pseudoprimes. I was merely thinking that most composites would "flunk" a base-5 psp test, which (I am assuming) is much faster than the Mod(x+2,1+x^2) test. This would greatly reduce the number of slower Mod(2 + x, 1 + x^2) tests that needed to be done in searching for psp's for that test.

[Dr Sardonicus]

As you can see from the following, I have obtained closed-form expressions for the coefficients of the degree-less-that-4 lift of Mod(1 + x, 1 + x^4)^n. They can be written as 4-term sums similar to the one already given. Unlike the constant term, though, the coefficient is a root of unity of degree greater than 1; a 4-th or 8-th root of unity. The trace may be written as a sum of algebraic conjugates; the conjugates of Mod(x, x^4 + 1) are Mod(x^3, x^4 + 1), Mod(-x, x^4 + 1), and Mod(-x^3, x^4 + 1). This allows the traces to be expressed as explicit 4-term sums. These expressions are unlikely to be useful computationally, but may be helpful theoretically.

? for(n=0,15,v=[lift(Mod(x + 1, x^4 + 1)^n),trace(Mod(-x, x^4 + 1)*Mod(1 + x, x^4+1)^n)/4, trace(Mod(-x^2, x^4 + 1)*Mod(x + 1, x^4 + 1)^n)/4, trace(Mod(-x^3, x^4 + 1)*Mod(x + 1, x^4 + 1)^n)/4, trace(Mod(x + 1, x^4 + 1)^n)/4];print(n" "v))
0 [1, 0, 0, 0, 1]
1 [x + 1, 0, 0, 1, 1]
2 [x^2 + 2*x + 1, 0, 1, 2, 1]
3 [x^3 + 3*x^2 + 3*x + 1, 1, 3, 3, 1]
4 [4*x^3 + 6*x^2 + 4*x, 4, 6, 4, 0]
5 [10*x^3 + 10*x^2 + 4*x - 4, 10, 10, 4, -4]
6 [20*x^3 + 14*x^2 - 14, 20, 14, 0, -14]
7 [34*x^3 + 14*x^2 - 14*x - 34, 34, 14, -14, -34]
8 [48*x^3 - 48*x - 68, 48, 0, -48, -68]
9 [48*x^3 - 48*x^2 - 116*x - 116, 48, -48, -116, -116]
10 [-164*x^2 - 232*x - 164, 0, -164, -232, -164]
11 [-164*x^3 - 396*x^2 - 396*x - 164, -164, -396, -396, -164]
12 [-560*x^3 - 792*x^2 - 560*x, -560, -792, -560, 0]
13 [-1352*x^3 - 1352*x^2 - 560*x + 560, -1352, -1352, -560, 560]
14 [-2704*x^3 - 1912*x^2 + 1912, -2704, -1912, 0, 1912]
15 [-4616*x^3 - 1912*x^2 + 1912*x + 4616, -4616, -1912, 1912, 4616]

If you want lift(lift(Mod(Mod(1,n)*x + 1, x^4 + 1)^k)) = (n-1)*x + 1, then trace(Mod(x + 1, x^4 + 1)^k)/4 has to be congruent to 1 (mod n); trace(Mod(-x^3, x^4 + 1)*Mod(x + 1, x^4 + 1)^k)/4 has to be congruent to -1 (mod n); and finally, trace(Mod(-x^2, x^4 + 1)*Mod(x + 1, x^4 + 1)^k)/4 and trace(Mod(-x, x^4 + 1)*Mod(1 + x, x^4+1)^k)/4 both have to be divisible by n.


EDIT: From the above data, you can see that for k == 6 (mod 8), the coefficient of x in lift((Mod(x + 1, x^4 + 1)^k) is zero; and if k == 4 (mod 8) the constant term is 0. I'm sure there's a straightforward proof, but I'm too lazy to work out the details

It is thus impossible to have lift(lift((Mod(Mod(1,n)*x + 1, x^4 + 1)^k)) = 1 - x for any n, if k is congruent to 4 or 6 (mod 8).

[Dr Sardonicus]

I finally thought of a very simple, straightforward proof of the "zero-ness" of the coefficients of x^3, x^2, x and 1 in lift(Mod(x+1, x^4 + 1)^k) for k == 2, 0, 6 and 4 (mod 8) respectively.

All that is required is numerical verification that four consecutive values are 0. The rest being 0 then follows because for any given r, the subsequence lift(Mod(x+1,x^4 + 1))^(8*n + r) satisfies a linear recurrence with constant coefficients of order 4. Boom! Done.

The characteristic polynomial is charpoly(Mod(x, x^4 - 4*x^3+6*x^2-4*x+2)^8)) = x^4 + 272*x^3 + 18528*x^2 + 4352*x + 256.

The characteristic polynomial x^4 + 272*x^3 + 18528*x^2 + 4352*x + 256 factors as (x^2 + 136*x + 16)^2. I am too lazy to check whether any of the subsequences of terms in a residue class mod 8 actually satisfy a linear recurrence of order 2.

[paulunderwood]

Powers of x over x^2-136*x+16 are interesting.

Mod(Mod(x,n),x^2-136*x+16)^(n+1)==16 is good for n%8==3 and n%8==5

I can also check Mod(Mod(x,n),x^2-136*x+16)^((n+1)/4)==2 for n%8==3, and Mod(Mod(x,n),x^2-136*x+16)^((n+1)/2)==4 for n%8==5.

The test Mod(Mod(x,n),x^2-136*x+16)^(n+1)==16 can be transformed into Mod(Mod(x,n),x^2-1154*x+1)^((n+1)/2)==1 for n%8={3, 5} for Fermat-2-PRP, making a quick check of Feitsma's 2^64 2-PRP possible.

As ever n%8==1 has psudoprimes. Without checking Feitsma, we now have simple tests for n%8 = {3,5,7}

[Dr Sardonicus]

For every integer r = 0 to 7, the sequence a_n = lift(Mod(x+1,x^4+1)^(8*n + r)), n = 0, 1, 2, ... satisfies the recurrence a_n+2+136*a_n+1 + 16*a_n = 0.

Thus, for any given r, the coefficients of 1, x, x^2 and x^3 in the lift are four sequences, each satisfying this recurrence. I have noted cases for even r where one of the four sequences is the zero sequence.

I note that the discriminant of the quadratic x^2 + 136*x + 16 is 136² - 4*16 = 128*144 = 2*8²*12².

Note that Mod(1 + x, 1 + x^2)^4 has the linear minimum polynomial x + 4 (that is, (1 + I)^4 = -4), and now we have that Mod(1 + x, 1 + x^4)^8 has the quadratic minimum polynomial x^2 + 136*x + 16. Hmm, that's funny...

I checked, and - sure enough! Mod(1 + x, 1 + x^8)^16 has a degree-4 minimum polynomial; and Mod(1 + x, 1 + x^16)^32 has a degree-8 minimum polynomial.

I'm sold. Mod(1 + x, 1 + x^(2^k))^(2^k+1) has minimum polynomial of degree 2^k-1. Hmm, in every case so far, the zeroes of the minimum polynomial are real...

EDIT: Of course they're all real. And there's nothing special about powers of two. We have

1 + exp(2*I*pi/n) = exp(2*I*pi/(2*n))*[exp(-2*I*pi/(2*n)) + exp(2*I*pi/(2*n))] = exp(2*I*pi/(2*n))*2*cos(2*pi/(2*n)).

This is a 2n-th root of unity times a real number. Raising to the n-th power gives a real number.