Is there such a thing as a probable composite test?

ixfd64 · 2021-10-29, 23:25

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.

retina · 2021-10-29, 23:37

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.

kruoli · 2021-10-29, 23:45

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.

a1call · 2021-10-29, 23:53

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.

Dr Sardonicus · 2021-10-30, 03:14

Quote:

Originally Posted by ixfd64

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.

chris2be8 · 2021-10-30, 15:40

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.

Dr Sardonicus · 2021-10-30, 16:22

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

firejuggler · 2021-10-30, 16:43

Technically any prime test pove it is a composite if it fail.

ixfd64 · 2021-10-31, 02:16

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.

Dr Sardonicus · 2021-11-01, 12:53

A probable prime test depends on a property which is

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

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

2021-10-29, 23:25	#1
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 2×3²×137 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:53	#4
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 8C2₁₆ 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-31, 02:16	#9
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 2·3²·137 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 3·41·47 Posts	A probable prime test depends on a property which is possessed 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 be possessed 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
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

2021-10-29, 23:37	#2
retina Undefined "The unspeakable one" Jun 2006 My evil lair 2³·3·269 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 983 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-30, 15:40	#6
chris2be8 Sep 2009 4432₈ 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 3×41×47 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 2839₁₀ Posts	Technically any prime test pove it is a composite if it fail.