20220609, 11:56  #1 
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^r1)^t)}1\] is xPRP, except for the cases x^2x1 and x2 and x1 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^r2. That is the expanded polynomial must have more than 2 terms. Example: n=18427 and f=x^3*(x^21)^21. Another: n=59 and f=x*(x^21)1. Another: n=29 and f=x^2*(x^21)1. Can you find a pseudoprime? Last fiddled with by paulunderwood on 20220609 at 13:29 
20220609, 21:13  #2 
Sep 2002
Database er0rr
11·389 Posts 

20220609, 23:43  #3 
Sep 2002
Database er0rr
1000010110111_{2} Posts 
Thinking about this x^3==x+1 and x+1  x^3x.
Now consider only trinomials: let f=x^ax^b1 (a>b, a>3) and gcd(a,b)==1. For example f=x^5x^31. Then x^5 == x^3+1 and gcd(x^3+1,x^5x^3) = 1. I am now brute force searching f=x^5x^31 for counterexample to x^n==x (mod n, f) Last fiddled with by paulunderwood on 20220610 at 00:24 
20220610, 01:30  #4 
Sep 2002
Database er0rr
10B7_{16} Posts 
Now consider f=x^4xc 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^4xc). I am searching for a counterexample. The above is wrong reasoning. I should say that if x^n == x (mod n, x^4xc) for some c: gcd(c,n)==1 then n is prime. Last fiddled with by paulunderwood on 20220610 at 02:44 
20220610, 10:09  #5  
Sep 2002
Database er0rr
11×389 Posts 
Quote:
Clinging on... now testing x^n == x (mod n, x^4xc) where positive n = a^4ac for a in N and gcd(c,n)==1. However now n is much larger. Edit: n = 40^4401535309 is a counterexample. Last fiddled with by paulunderwood on 20220610 at 10:32 

20220610, 11:55  #6 
Feb 2017
Nowhere
5974_{10} Posts 
The following may be pertinent:
Jon Grantham, There are infinitely many Perrin pseudoprimes, J. Number Theory 130 (2010) 11171128 \(\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{ CarmichaelFrobenius numbers with respect to }K\text{ which are less than }N\text{, for some }c\;=\;c(K)\;>\;0\text{.}\) 
20220610, 17:15  #7 
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:
(I pretest 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 20220610 at 18:54 
20220610, 21:55  #8 
Sep 2002
Database er0rr
4279_{10} Posts 
Let n = 2*(2^31)+c i.e. 14+c and test x^n = x (mod n, x*(x^31)+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^41)+c = 30+c over x*(x^41)+c and looks promising. But the Carmichael number 5559639084013801 fails. Last fiddled with by paulunderwood on 20220611 at 03:34 
20220611, 11:54  #9 
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*(x1)^3*(x^21)a*(a1)^3*(a^21); for(v=1,#V,n=V[v];if(Mod(Mod(x,n),f)^n==x,print([a,n]);break(2))))} Last fiddled with by paulunderwood on 20220611 at 13:57 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
I found the primality test, there seems to be no composite numbers that pass the test  sweety439  sweety439  7  20200211 19:49 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Double check LL test faster than first run test  lidocorc  Software  3  20081203 15:12 
Will the torture test, test ALL available memory?  swinster  Software  2  20071201 17:54 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 