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 NumberExplore with Wolfram|Alpha
WolframAlpha
More things to try:
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.Referenced on Wolfram|Alpha
Composite Number ProblemCite this as:
Weisstein, Eric W. "Composite Number Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CompositeNumberProblem.html