Thread: mod x^4+1
View Single Post
Old 2022-03-22, 19:36   #23
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·32·7·17 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote