mersenneforum.org > Math Is there such a thing as a probable composite test?
 Register FAQ Search Today's Posts Mark Forums Read

 2021-10-29, 23:25 #1 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 11×13×17 Posts 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
 2021-10-29, 23:37 #2 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2×3,167 Posts 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.
 2021-10-29, 23:45 #3 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 84010 Posts 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.
 2021-10-29, 23:53 #4 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 32×5×72 Posts 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
2021-10-30, 03:14   #5
Dr Sardonicus

Feb 2017
Nowhere

7·13·59 Posts

Quote:
 Originally Posted by ixfd64 Probably a stupid question, but is there such a thing as a probable composite test?
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.

 2021-10-30, 15:40 #6 chris2be8     Sep 2009 24×139 Posts 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.
 2021-10-30, 16:22 #7 Dr Sardonicus     Feb 2017 Nowhere 7·13·59 Posts 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).
 2021-10-30, 16:43 #8 firejuggler     "Vincent" Apr 2010 Over the rainbow AC116 Posts Technically any prime test pove it is a composite if it fail.
 2021-10-31, 02:16 #9 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 45778 Posts 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
 2021-11-01, 12:53 #10 Dr Sardonicus     Feb 2017 Nowhere 10100111110012 Posts A probable prime test depends on a property which ispossessed by all prime numbers possessed by only a small - perhaps an infinitesimal - proportion of composite numbers, and 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 bepossessed by all composite numbers possessed by only a small - perhaps an infinitesimal - proportion of prime numbers, and 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 9 2020-06-28 18:28 sweety439 sweety439 7 2020-02-11 19:49 SELROC Math 1 2019-07-31 09:54 mohdosa Information & Answers 22 2014-10-10 11:34 fenderbender Miscellaneous Math 22 2010-11-11 01:04

All times are UTC. The time now is 04:56.

Tue Jan 25 04:56:10 UTC 2022 up 185 days, 23:25, 0 users, load averages: 1.12, 1.17, 1.24