The composite number problem asks whether a given positive integer 
can be written as 
with integers 
and 
.
The complexity of the composite number problem was unknown for many years, although the problem was known to belong to 
(Pratt 1975, Garey and Johnson 1983).
Agrawal et al. (2004) gave a deterministic polynomial
time algorithm, the AKS
primality test, which decides whether an input is prime
or composite.
