検索に移動この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。素数であるか合成数であるかを判定する問題である。素数判定を行うアルゴリズムのことを素数判定法という。RSA暗号の鍵生成のように素数性の判定は応用上重要であるので、素数性を高速に判定するアルゴリズムは計算理論において強い関心の対象である。Saxenaにより発表された(AKS素数判定法)。理論上は大躍進であったが、計算量オーダーに関しては多項式の次数が高く、実用上はAPR判定法(英語版)などのほうが高速であることが多い。「合成数である」または「良く分からない」と判別する判定法がある。