mersenneforum.org mod x^4+1
 Register FAQ Search Today's Posts Mark Forums Read

2022-03-16, 01:06   #12
Dr Sardonicus

Feb 2017
Nowhere

22·3·499 Posts

Quote:
 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.

 2022-03-16, 05:45 #13 paulunderwood     Sep 2002 Database er0rr 22×32×7×17 Posts The companion matrix of x^4+1 is: Code: ? 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: Code: ? 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: Code: ? 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. Last fiddled with by paulunderwood on 2022-03-16 at 07:34
2022-03-16, 12:17   #14
Dr Sardonicus

Feb 2017
Nowhere

22×3×499 Posts

Quote:
 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.

Quote:
 Verified to 2^64 using Feitsma's list of 2-PSPs.
Well done, Sir!

 2022-03-16, 18:07 #15 paulunderwood     Sep 2002 Database er0rr 102748 Posts FWIW, not a peep out of: Code: {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]))))));} Last fiddled with by paulunderwood on 2022-03-16 at 18:16
2022-03-17, 01:29   #16
Dr Sardonicus

Feb 2017
Nowhere

135448 Posts

Quote:
 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.
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.

2022-03-17, 13:22   #17
paulunderwood

Sep 2002
Database er0rr

22·32·7·17 Posts

Quote:
 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.

 2022-03-17, 14:06 #18 Dr Sardonicus     Feb 2017 Nowhere 22·3·499 Posts Let Code: 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 $\frac{1}{4}\sum_{m=1}^{4}$$1 + e^{\frac{2\pi i(2m-1)}{8}$$^{n}$ 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. Last fiddled with by Dr Sardonicus on 2022-03-18 at 01:50 Reason: Fix bad notation;correct misstatement
 2022-03-18, 15:02 #19 Dr Sardonicus     Feb 2017 Nowhere 135448 Posts 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. Code: ? 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). Last fiddled with by Dr Sardonicus on 2022-03-18 at 16:50
 2022-03-20, 15:08 #20 Dr Sardonicus     Feb 2017 Nowhere 10111011001002 Posts "That's the stupidest proof I've ever seen in my life!" 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.
 2022-03-20, 21:13 #21 paulunderwood     Sep 2002 Database er0rr 10BC16 Posts 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} Last fiddled with by paulunderwood on 2022-03-20 at 21:51
 2022-03-21, 13:14 #22 Dr Sardonicus     Feb 2017 Nowhere 135448 Posts For every integer r = 0 to 7, the sequence an = lift(Mod(x+1,x^4+1)^(8*n + r)), n = 0, 1, 2, ... satisfies the recurrence an+2+136*an+1 + 16*an = 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 1362 - 4*16 = 128*144 = 2*82*122. 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^(2k))^(2k+1) has minimum polynomial of degree 2k-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. Last fiddled with by Dr Sardonicus on 2022-03-21 at 13:39

All times are UTC. The time now is 15:40.

Sat Oct 1 15:40:49 UTC 2022 up 44 days, 13:09, 1 user, load averages: 1.25, 1.22, 1.52