Composite Number Problem

The composite number problem asks if for a given positive integer N there exist positive integers m and n such that N=mn.

The complexity of the composite number problem was unknown for many years, although the problem was known to belong to NP intersection co-NP (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.

See also

AKS Primality Test, Composite Number

Explore with Wolfram|Alpha


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.

Cite this as:

Weisstein, Eric W. "Composite Number Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications