Compositeness

This article page is a stub, please help by expanding it.

Compositeness is the quality of an integer being a composite number.

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 $\scriptstyle n\,$ 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 $\scriptstyle {\frac {n-1}{2}}\,$ 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

• Fermat pseudoprimes
• Carmichael numbers

• Primality (the quality of an integer being a prime number)