mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2022-06-09, 11:56   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29×151 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2022-06-09, 21:13   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

104338 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

Can you find a pseudoprime?
Composite n=27664033 is x^n==x (mod n, x^3-x-1).
paulunderwood is offline   Reply With Quote
Old 2022-06-09, 23:43   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29·151 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Composite n=27664033 is x^n==x (mod n, x^3-x-1).
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
paulunderwood is offline   Reply With Quote
Old 2022-06-10, 01:30   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29·151 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-06-10, 10:09   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

111B16 Posts
Default

Quote:
Originally Posted by paulunderwood View Post

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
paulunderwood is offline   Reply With Quote
Old 2022-06-10, 11:55   #6
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

137308 Posts
Default

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{.}\)
Dr Sardonicus is offline   Reply With Quote
Old 2022-06-10, 17:15   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29·151 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-06-10, 21:55   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29×151 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2022-06-11, 11:54   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

29×151 Posts
Default

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
paulunderwood is offline   Reply With Quote
Reply

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 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

All times are UTC. The time now is 06:54.


Wed Dec 7 06:54:07 UTC 2022 up 111 days, 4:22, 0 users, load averages: 0.83, 1.01, 0.94

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.

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