mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2021-10-29, 23:25   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

11×13×17 Posts
Default Is there such a thing as a probable composite test?

Probably a stupid question, but is there such a thing as a probable composite test?

A probable prime is defined as an integer that satisfies a specific condition that is satisfied by all primes but not most composite numbers. I did some searching and couldn't find anything about tests that determine whether a number is probably composite.

Last fiddled with by ixfd64 on 2021-10-29 at 23:28 Reason: reword
ixfd64 is offline   Reply With Quote
Old 2021-10-29, 23:37   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

5·7·181 Posts
Default

It depends upon your threshold for "probable".

Consider this test for probable compositeness: N is input. Output "PRC".

I don't even need to use N, and for "most" inputs the answer will be correct. With the expected correctness increasing as N increases. And if N is even then there will be at most only a single false output.
retina is online now   Reply With Quote
Old 2021-10-29, 23:45   #3
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

23·3·5·7 Posts
Default

Consider the Fermat PRP test, it is quite simple. If there would be a PRC test, GIMPS would use this if it would be more efficient. This on its own does not proof anything of course.
kruoli is offline   Reply With Quote
Old 2021-10-29, 23:53   #4
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

220710 Posts
Default

I think it is important to note that in regular context Probable is not usually interchangeable with possible, but in Probabilistic-Primality test it generally-could-be. All Mersenne numbers are Probable-Prime for all bases 2^n, n>1.
However very few are probably prime in the general sense of what probable (likely) is.
Interesting question though. I would like to have expert input, but I think Primality-Tests are either Deterministic or Probabilistic in which (the latter) case the integer is possibly (possible-to-be) composite if the test is positive and definitely composite otherwise.

Last fiddled with by a1call on 2021-10-30 at 00:03
a1call is offline   Reply With Quote
Old 2021-10-30, 03:14   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

123758 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
Probably a stupid question, but is there such a thing as a probable composite test?
<snip>
My short answer would be no.

Note, however, that there is something better: any number which "fails" a probable prime test is certain to be composite. And certain beats "probable" any day of the week.
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-30, 15:40   #6
chris2be8
 
chris2be8's Avatar
 
Sep 2009

8B016 Posts
Default

A probable composite test would be some condition that most primes fail so a number passing it is more likely to be composite that a number that fails it.

A simple example would be checking if the low bit is 0 (ie it's an even number). The only even prime is 2 so most numbers meeting that condition are composite.

But I don't know of any such test that would be useful for real work.
chris2be8 is offline   Reply With Quote
Old 2021-10-30, 16:22   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

123758 Posts
Default

I suppose you could say that a number is "probably composite" if it is greater than 14. This is because 14 is the largest integer such that at least half the positive integers less than it are not composite.

Less facetiously (but only slightly less) would be to say that any "large" number is "probably composite," in the sense that for large N, the density of primes "near" N is around 1/log(N) (natural log).
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-30, 16:43   #8
firejuggler
 
firejuggler's Avatar
 
"Vincent"
Apr 2010
Over the rainbow

2,753 Posts
Default

Technically any prime test pove it is a composite if it fail.
firejuggler is offline   Reply With Quote
Old 2021-10-31, 02:16   #9
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

11·13·17 Posts
Default

The prime number theorem does mean that almost all positive integers are composite. But it doesn't look like there is a test that makes the determination that a number is "probably" composite based on its properties.

Last fiddled with by ixfd64 on 2021-10-31 at 03:27
ixfd64 is offline   Reply With Quote
Old 2021-11-01, 12:53   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

33×199 Posts
Default

A probable prime test depends on a property which is
  1. possessed by all prime numbers
  2. possessed by only a small - perhaps an infinitesimal - proportion of composite numbers, and
  3. is computationally cheap to verify.
As has already been pointed out at least twice in this thread, a number which "fails" a probable prime test is certain to be composite.

By analogy, a "probable composite test" would depend on some property which (if there were such a property) would be
  1. possessed by all composite numbers
  2. possessed by only a small - perhaps an infinitesimal - proportion of prime numbers, and
  3. is computationally cheap to verify.
Assuming this is what the OP intended, a consequence would be that any number which "fails" the test would be certain to be prime.

That would be nice, but I'm not holding my breath...
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Composite test for n == 3 mod 4 paulunderwood Miscellaneous Math 9 2020-06-28 18:28
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
Conference paper: On the Combined Fermat/Lucas Probable Prime Test SELROC Math 1 2019-07-31 09:54
Hi, how can I test my probable prime number? mohdosa Information & Answers 22 2014-10-10 11:34
Miller-Rabin Strong Probable Prime Test (SPRP) fenderbender Miscellaneous Math 22 2010-11-11 01:04

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


Wed Jan 26 09:06:40 UTC 2022 up 187 days, 3:35, 0 users, load averages: 1.42, 1.50, 1.49

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.

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