 mersenneforum.org A test for primality?
 Register FAQ Search Today's Posts Mark Forums Read 2022-06-09, 11:56 #1 paulunderwood   Sep 2002 Database er0rr 22·1,063 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

22×1,063 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

109C16 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 22·1,063 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

22·1,063 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 22·3·491 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 10000100111002 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 22×1,063 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 22·1,063 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 23:14.

Tue Aug 9 23:14:46 UTC 2022 up 33 days, 18:02, 1 user, load averages: 2.65, 2.23, 1.94