 mersenneforum.org A test for primality?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2022-06-09, 11:56 #1 paulunderwood   Sep 2002 Database er0rr 11×389 Posts A test for primality? Over the years I have never found a counterexample to: For integers x>1, s>=0, all r>0, all t>0, odd and irreducible $f=(x^s\times\prod_{r,t}{(x^r-1)^t)}-1$ is x-PRP, except for the cases x^2-x-1 and x-2 and x-1 and -1. What I now propose is that the above function can be used for a primality for n if x^n==x mod (n,f), with the further restriction of discounting x^r-2. That is the expanded polynomial must have more than 2 terms. Example: n=18427 and f=x^3*(x^2-1)^2-1. Another: n=59 and f=x*(x^2-1)-1. Another: n=29 and f=x^2*(x^2-1)-1. Can you find a pseudoprime? Last fiddled with by paulunderwood on 2022-06-09 at 13:29   2022-06-09, 21:13   #2
paulunderwood

Sep 2002
Database er0rr

11·389 Posts Quote:
 Originally Posted by paulunderwood Can you find a pseudoprime?
Composite n=27664033 is x^n==x (mod n, x^3-x-1).    2022-06-09, 23:43   #3
paulunderwood

Sep 2002
Database er0rr

10000101101112 Posts Quote:
 Originally Posted by paulunderwood Composite n=27664033 is x^n==x (mod n, x^3-x-1). Now consider only trinomials: let f=x^a-x^b-1 (a>b, a>3) and gcd(a,b)==1. For example f=x^5-x^3-1. Then x^5 == x^3+1 and gcd(x^3+1,x^5-x^3) = 1.

I am now brute force searching f=x^5-x^3-1 for counterexample to x^n==x (mod n, f) Last fiddled with by paulunderwood on 2022-06-10 at 00:24   2022-06-10, 01:30 #4 paulunderwood   Sep 2002 Database er0rr 10B716 Posts Now consider f=x^4-x-c where gcd(c,n)==1. So to test odd "n" for primality find a "c" with gcd(c,n)==1 and compute x^n == x (mod n, x^4-x-c). I am searching for a counterexample. The above is wrong reasoning. I should say that if x^n == x (mod n, x^4-x-c) for some c: gcd(c,n)==1 then n is prime. Last fiddled with by paulunderwood on 2022-06-10 at 02:44   2022-06-10, 10:09   #5
paulunderwood

Sep 2002
Database er0rr

11×389 Posts Quote:
 Originally Posted by paulunderwood The above is wrong reasoning. I should say that if x^n == x (mod n, x^4-x-c) for some c: gcd(c,n)==1 then n is prime.
n=49141 and c=14695 is a counterexample.

Clinging on... now testing x^n == x (mod n, x^4-x-c) where positive n = a^4-a-c for a in N and gcd(c,n)==1. However now n is much larger.

Edit: n = 40^4-40-1535309 is a counterexample.

Last fiddled with by paulunderwood on 2022-06-10 at 10:32   2022-06-10, 11:55 #6 Dr Sardonicus   Feb 2017 Nowhere 597410 Posts The following may be pertinent: Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 1117-1128 $$\text{Theorem 1.1. Let }f (x)\;\in\;\mathbb{Z}[x]\text{ be a monic, squarefree polynomial with splitting field }K\text{. There are infinitely many Frobenius pseudoprimes with respect to }f(x)\text{.}\\ \\ \text{In fact, there are } \gg\;N^{c}\text{ Carmichael-Frobenius numbers with respect to }K\text{ which are less than }N\text{, for some }c\;=\;c(K)\;>\;0\text{.}$$   2022-06-10, 17:15 #7 paulunderwood   Sep 2002 Database er0rr 11·389 Posts Thanks for that link/info Dr. Sardoncus. I am unsure whether it is applicable or not. I am now testing a quintic case on two fronts with gcd(c,n)==1 and positive n: x^n == x (mod n, x^5-x-c) x^n == x (mod n, x^5-x-c) where n=a^5-a-c (I pre-test with Mod(c,n)^n==c.) Later... The first failed with [n,c]=[146611, 33064]. The second fails with [n,c]=[972471151, 101270609]. Last fiddled with by paulunderwood on 2022-06-10 at 18:54   2022-06-10, 21:55 #8 paulunderwood   Sep 2002 Database er0rr 427910 Posts Let n = 2*(2^3-1)+c i.e. 14+c and test x^n = x (mod n, x*(x^3-1)+c). Note this is not a necessary condition but I claim it is sufficient. Testing... [n,c]=[280067761, 280067747] is a counterexample. I am now testing n = 2*(2^4-1)+c = 30+c over x*(x^4-1)+c and looks promising. But the Carmichael number 5559639084013801 fails. Last fiddled with by paulunderwood on 2022-06-11 at 03:34   2022-06-11, 11:54 #9 paulunderwood   Sep 2002 Database er0rr 11×389 Posts I am running the following against Feitsma's Carmichael numbers list (2^64) with good results: Code: {for(a=3,1000,print([a]);f=x*(x-1)^3*(x^2-1)-a*(a-1)^3*(a^2-1); for(v=1,#V,n=V[v];if(Mod(Mod(x,n),f)^n==x,print([a,n]);break(2))))} [a,n]=[37, 1742800894240715521] fails. Last fiddled with by paulunderwood on 2022-06-11 at 13:57  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 Trilo Miscellaneous Math 25 2018-03-11 23:20 lidocorc Software 3 2008-12-03 15:12 swinster Software 2 2007-12-01 17:54 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 20:47.

Sun Sep 25 20:47:09 UTC 2022 up 38 days, 18:15, 0 users, load averages: 0.88, 1.01, 1.02

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.

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