20211029, 23:25  #1 
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 20211029 at 23:28 Reason: reword 
20211029, 23:37  #2 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6326_{10} 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. 
20211029, 23:45  #3 
"Oliver"
Sep 2017
Porta Westfalica, DE
3·277 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.

20211029, 23:53  #4 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2^{2}·3^{2}·61 Posts 
I think it is important to note that in regular context Probable is not usually interchangeable with possible, but in ProbabilisticPrimality test it generallycouldbe. All Mersenne numbers are ProbablePrime 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 PrimalityTests are either Deterministic or Probabilistic in which (the latter) case the integer is possibly (possibletobe) composite if the test is positive and definitely composite otherwise. Last fiddled with by a1call on 20211030 at 00:03 
20211030, 03:14  #5  
Feb 2017
Nowhere
5×1,069 Posts 
Quote:
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. 

20211030, 15:40  #6 
Sep 2009
4256_{8} 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. 
20211030, 16:22  #7 
Feb 2017
Nowhere
5×1,069 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). 
20211030, 16:43  #8 
"Vincent"
Apr 2010
Over the rainbow
2·3·457 Posts 
Technically any prime test pove it is a composite if it fail.

20211031, 02:16  #9 
Bemusing Prompter
"Danny"
Dec 2002
California
97F_{16} 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 20211031 at 03:27 
20211101, 12:53  #10 
Feb 2017
Nowhere
5·1,069 Posts 
A probable prime test depends on a property which is
By analogy, a "probable composite test" would depend on some property which (if there were such a property) would be
That would be nice, but I'm not holding my breath... 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Composite test for n == 3 mod 4  paulunderwood  Miscellaneous Math  9  20200628 18:28 
I found the primality test, there seems to be no composite numbers that pass the test  sweety439  sweety439  7  20200211 19:49 
Conference paper: On the Combined Fermat/Lucas Probable Prime Test  SELROC  Math  1  20190731 09:54 
Hi, how can I test my probable prime number?  mohdosa  Information & Answers  22  20141010 11:34 
MillerRabin Strong Probable Prime Test (SPRP)  fenderbender  Miscellaneous Math  22  20101111 01:04 