The composite number problem asks if for a given positive integer  there exist positive integers  and  such that .

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) subsequently and unexpectedly discovered a polynomial-time algorithm now known as the AKS primality test.

REFERENCES:

Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-157 and 288, 1983.

Miller, G. "Riemann's Hypothesis and Tests for Primality." J. Comp. Syst. Sci. 13, 300-317, 1976.

Pratt, V. "Every Prime Has a Succinct Certificate." SIAM J. Comput. 4, 214-220, 1975.