mod x^4+1
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.
I propose the test Mod(Mod(x+1,n),x^4+1)^(n1) for odd n with the following results[LIST][*]n%8==1: 1: counterexamples exist.[*]n%8==3: x^2x+1[*]n%8==5: x^3+x^2x[*]n%8==7: x^3[/LIST] 
[QUOTE=paulunderwood;601648]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.
I propose the test Mod(Mod(x+1,n),x^4+1)^(n1) for odd n with the following results[LIST][*]n%8==1: 1: counterexamples exist.[*]n%8==3: x^2x+1[*]n%8==5: x^3+x^2x[*]n%8==7: x^3[/LIST][/QUOTE] I was able to prove that the indicated congruences indeed hold if n is a prime congruent to 3, 5, or 7 (mod 8). It made an interesting exercise. So there are no counterexamples to these with n prime :smile: I have no idea how to try to construct composite n congruent to 3, 5, or 7 (mod 8) for which these congruences hold. [b]EDIT:[/b] BTW, the test for numbers congruent to 1 (mod 4) corresponding to the test you gave for numbers congruent to 3 (mod 4) is lift(lift(Mod(Mod(1,n)*x + 2,x^2 + 1)^(n1))) == 1. Every prime congruent to 1 (mod 4) other than 5 satisfies this condition. (Why 5 is exceptional is left as an exercise for the reader.) But the condition is rife with pseudoprimes, as the following mindless sweep shows: [code]? forstep(n=5,100000,4,r=lift(lift(Mod(Mod(1,n)*x+2,x^2+1)^(n1)));if(r==1&&!ispseudoprime(n),print(n" "factor(n)))) 15841 [7, 1; 31, 1; 73, 1] 29341 [13, 1; 37, 1; 61, 1] 38081 [113, 1; 337, 1] 40501 [101, 1; 401, 1] 41041 [7, 1; 11, 1; 13, 1; 41, 1] 46657 [13, 1; 37, 1; 97, 1] 75361 [11, 1; 13, 1; 17, 1; 31, 1][/code] For the mod x^4 + 1 test for numbers congruent to 1 (mod 8), we have [code]? forstep(n=9,500000,8,r=lift(lift(Mod(Mod(1,n)*x+1,x^4+1)^(n1)));if(r==1&&!ispseudoprime(n),print(n" "factor(n)))) 15841 [7, 1; 31, 1; 73, 1] 162401 [17, 1; 41, 1; 233, 1] 410041 [41, 1; 73, 1; 137, 1][/code] It occurred to me that a test of numbers congruent to 1 (mod m) based on the cyclotomic polynomial for the primitive mth roots of unity will also be rife with pseudoprimes. The reason is that it is well known that there are infinitely many Carmichael numbers whose factors are all congruent to 1 (mod m). Any such Carmichael number (with the possible exceptions of those divisible by a finite set of primes) will be a pseudoprime for such a test. Note, however, that although 15841 is a Carmichael number, not all its factors are congruent to 1 (mod 4). And two of the pseudoprimes for the mod x^2 + 1 test only have two prime factors, so are automatically not Carmichael numbers. 
The test over x^2+1 can be computed with 2 Selfridges. Over x^4+1 it is 8 Selfridges by combining the difference of squares:
[CODE]? Mod(s*x^3+t*x^2+u*x+v,x^4+1)^2 Mod((2*v*s + 2*u*t)*x^3 + (s^2 + (2*v*t + u^2))*x^2 + (2*t*s + 2*v*u)*x + (2*u*s + (t^2 + v^2)), x^4 + 1) ? Mod(s*x^3+t*x^2+u*x+v,x^4+1)*(x+1) Mod((s + t)*x^3 + (t + u)*x^2 + (u + v)*x + (s + v), x^4 + 1) [/CODE] where s,t,u and v are intermediate values during leftright binary exponentiation. (x+1) is the base. 
[QUOTE=paulunderwood;601648]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> [/QUOTE]Just out of curiosity, up to what limit has this been checked? 
[QUOTE=Dr Sardonicus;601723]Just out of curiosity, up to what limit has this been checked?[/QUOTE]
I have checked the n%3==4 test over x^2+1 up to 2^50. The others I tend to test up to 10^8  takes a minute or two. Furthermore, for n%4==3 I can test base x+2 over x^2+1, for n%8==5 base x+1 over x^4+1, for n%16==9 base x+1 over x^8+1 and so on, with the number of Selfridges ballooning. 
[QUOTE=paulunderwood;601725]I have checked the n%3==4 test over x^2+1 up to 2^50.[/quote]Hmm. Might be time to start thinking about how to [i]construct[/i] composite n that "fool" the test.
[quote]The others I tend to test up to 10^8  takes a minute or two.[/quote]If you turn up pseudoprimes < 10^8, I'd say abandon that test. [quote]Furthermore, for n%4==3 I can test base x+2 over x^2+1, for n%8==5 base x+1 over x^4+1, for n%16==9 base x+1 over x^8+1 and so on, with the number of Selfridges ballooning.[/QUOTE]How many tests lift(lift(Mod(Mod(1,n)*x,x^2  a*x + 1)^(n+1)))==1 with avalues such that kronecker(a^2  4, n) == 1 could you run for the same number of Selfridges? (I'm assuming the computational cost of determining such avalues is negligible in comparison. I am also disregarding any pertinent gcd(poly in a, n) conditions which I assume are likewise computationally very cheap.) 
[QUOTE=Dr Sardonicus;601781]
How many tests lift(lift(Mod(Mod(1,n)*x,x^2  a*x + 1)^(n+1)))==1 with avalues such that kronecker(a^2  4, n) == 1 could you run for the same number of Selfridges? (I'm assuming the computational cost of determining such avalues is negligible in comparison. I am also disregarding any pertinent gcd(poly in a, n) conditions which I assume are likewise computationally very cheap.)[/QUOTE] That is easy for testing x+1 over x^4+1; It is 8/2=4 times the number of Selfridges of x over x^2a*x+1 (with (a^24  n)==1). I have not computed the function for x^2^k+1, but it gets big! 
Considering n%8==5 with Mod(Mod(x+1,n),x^4+1)^n==1x as the main test, can you find any k such that Mod(Mod(x+1,n),x^4+1)^k==1x for composite n?

[QUOTE=paulunderwood;601787]Considering n%8==5 with Mod(Mod(x+1,n),x^4+1)^n==1x as the main test, can you find any k such that Mod(Mod(x+1,n),x^4+1)^k==1x for composite n?[/QUOTE](checks, OK, it's equivalent to test proposed earlier in thread).
Evidently, none up to 10^8 since you've tested that far. I don't intend to do a numerical sweep above that point, so if you want more searching above 10^8, you'll have to do it yourself or get someone else to do it. I have been thinking about ways to [i]construct[/i] pseudoprimes  but no good ideas yet. 
[QUOTE=Dr Sardonicus;601789](checks, OK, it's equivalent to test proposed earlier in thread).
Evidently, none up to 10^8 since you've tested that far. I don't intend to do a numerical sweep above that point, so if you want more searching above 10^8, you'll have to do it yourself or get someone else to do it. I have been thinking about ways to [i]construct[/i] pseudoprimes  but no good ideas yet.[/QUOTE] I did say "any k". Powers k never seem to map x+1 to 1x. HTH. 
[QUOTE=Dr Sardonicus;601781]
If you turn up pseudoprimes < 10^8, I'd say abandon that test. [/QUOTE] n%8==5 tested up to n<10^10. I will take it to the next exponent. 
All times are UTC. The time now is 21:54. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2022, Jelsoft Enterprises Ltd.