![]() |
![]() |
#1 |
Sep 2002
Database er0rr
22×1,063 Posts |
![]()
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 |
![]() |
![]() |
![]() |
#2 |
Sep 2002
Database er0rr
109C16 Posts |
![]() |
![]() |
![]() |
![]() |
#3 |
Sep 2002
Database er0rr
102348 Posts |
![]()
Thinking about this x^3==x+1 and x+1 | x^3-x.
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 |
![]() |
![]() |
![]() |
#4 |
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 |
![]() |
![]() |
![]() |
#5 | |
Sep 2002
Database er0rr
22×1,063 Posts |
![]() Quote:
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 |
|
![]() |
![]() |
![]() |
#6 |
Feb 2017
Nowhere
24×32×41 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{.}\) |
![]() |
![]() |
![]() |
#7 |
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:
(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 |
![]() |
![]() |
![]() |
#8 |
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. ![]() Last fiddled with by paulunderwood on 2022-06-11 at 03:34 |
![]() |
![]() |
![]() |
#9 |
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))))} Last fiddled with by paulunderwood on 2022-06-11 at 13:57 |
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
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 | 2020-02-11 19:49 |
Modifying the Lucas Lehmer Primality Test into a fast test of nothing | Trilo | Miscellaneous Math | 25 | 2018-03-11 23:20 |
Double check LL test faster than first run test | lidocorc | Software | 3 | 2008-12-03 15:12 |
Will the torture test, test ALL available memory? | swinster | Software | 2 | 2007-12-01 17:54 |
A primality test for Fermat numbers faster than Pépin's test ? | T.Rex | Math | 0 | 2004-10-26 21:37 |