mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-03-13, 13:39   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Cool 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)^(n-1) for odd n with the following results
  • n%8==1: 1: counterexamples exist.
  • n%8==3: x^2-x+1
  • n%8==5: -x^3+x^2-x
  • n%8==7: -x^3

Last fiddled with by paulunderwood on 2022-03-13 at 13:43
paulunderwood is offline   Reply With Quote
Old 2022-03-13, 18:51   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5·7·132 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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)^(n-1) for odd n with the following results
  • n%8==1: 1: counterexamples exist.
  • n%8==3: x^2-x+1
  • n%8==5: -x^3+x^2-x
  • n%8==7: -x^3
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

I have no idea how to try to construct composite n congruent to 3, 5, or 7 (mod 8) for which these congruences hold.

EDIT: 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)^(n-1))) == 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)^(n-1)));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]
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)^(n-1)));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]
It occurred to me that a test of numbers congruent to 1 (mod m) based on the cyclotomic polynomial for the primitive m-th 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.

Last fiddled with by Dr Sardonicus on 2022-03-14 at 01:05
Dr Sardonicus is online now   Reply With Quote
Old 2022-03-14, 04:47   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

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)
where s,t,u and v are intermediate values during left-right binary exponentiation. (x+1) is the base.
paulunderwood is offline   Reply With Quote
Old 2022-03-14, 12:36   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

171B16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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>
Just out of curiosity, up to what limit has this been checked?
Dr Sardonicus is online now   Reply With Quote
Old 2022-03-14, 13:17   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10000100111002 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Just out of curiosity, up to what limit has this been checked?
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.

Last fiddled with by paulunderwood on 2022-03-14 at 13:25
paulunderwood is offline   Reply With Quote
Old 2022-03-15, 14:22   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

5·7·132 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
I have checked the n%3==4 test over x^2+1 up to 2^50.
Hmm. Might be time to start thinking about how to construct composite n that "fool" the test.

Quote:
The others I tend to test up to 10^8 -- takes a minute or two.
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.
How many tests

lift(lift(Mod(Mod(1,n)*x,x^2 - a*x + 1)^(n+1)))==1

with a-values 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 a-values is negligible in comparison. I am also disregarding any pertinent gcd(poly in a, n) conditions which I assume are likewise computationally very cheap.)
Dr Sardonicus is online now   Reply With Quote
Old 2022-03-15, 14:51   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
How many tests

lift(lift(Mod(Mod(1,n)*x,x^2 - a*x + 1)^(n+1)))==1

with a-values 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 a-values is negligible in comparison. I am also disregarding any pertinent gcd(poly in a, n) conditions which I assume are likewise computationally very cheap.)
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^2-a*x+1 (with (a^2-4 | n)==-1). I have not computed the function for x^2^k+1, but it gets big!

Last fiddled with by paulunderwood on 2022-03-15 at 14:52
paulunderwood is offline   Reply With Quote
Old 2022-03-15, 15:05   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

102348 Posts
Default

Considering n%8==5 with Mod(Mod(x+1,n),x^4+1)^n==1-x as the main test, can you find any k such that Mod(Mod(x+1,n),x^4+1)^k==1-x for composite n?

Last fiddled with by paulunderwood on 2022-03-15 at 15:07
paulunderwood is offline   Reply With Quote
Old 2022-03-15, 15:16   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

10111000110112 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Considering n%8==5 with Mod(Mod(x+1,n),x^4+1)^n==1-x as the main test, can you find any k such that Mod(Mod(x+1,n),x^4+1)^k==1-x for composite n?
(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 construct pseudoprimes - but no good ideas yet.
Dr Sardonicus is online now   Reply With Quote
Old 2022-03-15, 15:23   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

10000100111002 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
(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 construct pseudoprimes - but no good ideas yet.
I did say "any k". Powers k never seem to map x+1 to 1-x. HTH.

Last fiddled with by paulunderwood on 2022-03-15 at 15:26
paulunderwood is offline   Reply With Quote
Old 2022-03-15, 23:29   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

109C16 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post

If you turn up pseudoprimes < 10^8, I'd say abandon that test.
n%8==5 tested up to n<10^10. I will take it to the next exponent.

Last fiddled with by paulunderwood on 2022-03-15 at 23:29
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 11:41.


Thu Aug 18 11:41:45 UTC 2022 up 9:10, 0 users, load averages: 1.02, 1.19, 1.17

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔