合數問題詢問對於給定的正整數 
，是否存在正整數 
和 
使得 
。
合數問題的複雜性多年來一直未知，儘管已知該問題屬於 
(Pratt 1975, Garey and Johnson 1983)。Agrawal et al. (2004) 隨後出人意料地發現了一種多項式時間演算法，現在稱為 AKS 素性測試。
合數問題
參見
AKS 素性測試, 合數使用 探索
參考文獻
Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-157 和 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。請引用為
Weisstein, Eric W. "合數問題。" 來自 Web 資源。 https://mathworld.tw/CompositeNumberProblem.html