This site is supported by donations to The OEIS Foundation.
Compositeness
Compositeness is the quality of an integer being a composite number.
Contents
Compositeness testing
A compositeness test is a probabilistic compositeness test: if this test determines that a number is probably composite, it must be highly probable to be so.
If such a test falsely determines that a number is composite, would this number be called a pseudocomposite for that test? — Daniel Forgues 07:19, 7 November 2011 (UTC)
Compositeness testing algorithms
Fermat compositeness test
The Fermat compositeness test is done by applying Fermat's little theorem. If this test determines that an odd number is composite, it is guaranteed to be so, otherwise the number is either a prime or a Carmichael number (if all coprime bases from 2 to are considered, otherwise a Fermat pseudoprime to all coprime bases considered.)
Cf. Primality#Fermat primality test.
Compositeness proving
A compositeness proof is a deterministic compositeness test: if this test determines that a number is composite, it must be guaranteed to be so.
Compositeness proving algorithms
Trial division test
Cf. Primality#Trial division test.
AKS compositeness test
Cf. Primality#AKS primality test.
Elliptic curve compositeness proving
Cf. Primality#Elliptic curve primality proving.
See also
- Primality (the quality of an integer being a prime number)