20220322, 19:36  #23  
Sep 2002
Database er0rr
7×23×29 Posts 
Quote:
(n%8==3n%8==5)&&Mod(Mod(x,n),x^21154*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^220*x+2 with discriminant 2*2^2*3^2. Fietsma's list check out with Euler 2PSPs against (n%8==3n%8==5)&&Mod(Mod(x,n),x^2198*x+1)^((n+1)/2)==kronecker(2,n). Last fiddled with by paulunderwood on 20220322 at 20:01 

20220322, 19:43  #24 
Feb 2017
Nowhere
5·1,277 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 a_{k} be the coefficient of x in lift(Mod(1 + x, x^2  2)^k). This is a "Fibonaccilike" sequence: a_{0} = 0, a_{1} = 1, and a_{k+2} = 2*a_{k+1} + a_{k}. Starting with a_{1} 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_{3} = 5 and 13 divides a_{7} = 169, but 21 does not divide a_{11} = 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 base2 pseudoprime.) 
20220322, 22:14  #25 
Sep 2002
Database er0rr
7×23×29 Posts 
I don't see why it has to be base 2 Fermat PRP; The norm is 1.
Last fiddled with by paulunderwood on 20220322 at 22:53 
20220323, 00:07  #26  
Feb 2017
Nowhere
5×1,277 Posts 
Quote:
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 2psp but does satisfy my "reduced" condition. I note that 341, a 2psp congruent to 5 (mod 8), does not satisfy my "reduced" condition. So combining 2psp with my "reduced" condition may work fairly well for n == 5 (mod 8), but I suspect there are 2psp'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). 

20220323, 13:01  #27 
Feb 2017
Nowhere
5×1,277 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 + 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_{(n1)/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^22)^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 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)^((n3)/8) * 2^((n3)/4) * L_{(n1)/2} == 1 (mod n) n == 5 (mod 8) n divides F_{(n+1)/2} and (1)^((n+3)/8) * 2^((n+3)/4) * F_{(n1)/4} * L_{(n1)/4} == 1 (mod n) Note: Second condition can be restated as (1)^((n+3)/8) * 2^((n1)/4) * F_{(n1)/2} == 1 (mod n) n == 7 (mod 8) n divides L_{(n1)/2} and (1)^((n+1)/8) * 2^((n3)/4) * L_{(n+1)/2} == 1 (mod n) Last fiddled with by Dr Sardonicus on 20220324 at 00:03 Reason: Forgot exponents! and update 