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

2022-03-22, 19:36   #23
paulunderwood

Sep 2002
Database er0rr

23·3·11·17 Posts

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

Last fiddled with by paulunderwood on 2022-03-22 at 20:01

 2022-03-22, 19:43 #24 Dr Sardonicus     Feb 2017 Nowhere 2·3·17·61 Posts 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 ak be the coefficient of x in lift(Mod(1 + x, x^2 - 2)^k). This is a "Fibonacci-like" sequence: a0 = 0, a1 = 1, and ak+2 = 2*ak+1 + ak. Starting with a1 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 a3 = 5 and 13 divides a7 = 169, but 21 does not divide a11 = 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.)
 2022-03-22, 22:14 #25 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 Posts I don't see why it has to be base 2 Fermat PRP; The norm is -1. Last fiddled with by paulunderwood on 2022-03-22 at 22:53
2022-03-23, 00:07   #26
Dr Sardonicus

Feb 2017
Nowhere

184E16 Posts

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

 2022-03-23, 13:01 #27 Dr Sardonicus     Feb 2017 Nowhere 2×3×17×61 Posts 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 + Lk 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. Code: ? 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) Last fiddled with by Dr Sardonicus on 2022-03-24 at 00:03 Reason: Forgot exponents! and update

All times are UTC. The time now is 16:02.

Thu Feb 2 16:02:25 UTC 2023 up 168 days, 13:30, 1 user, load averages: 1.36, 1.10, 0.98