質數判定屬於 P（PRIMES is in P）
/ PRYMES /
問「這個數是質數嗎？」聽起來簡單，但它藏著一個關於輸入大小的尖銳微妙之處，而它的歷史是複雜度理論中最乾淨的勝利之一。問題 PRIMES 是這個決定問題：給定一個以二進位寫下的數 N，若 N 是質數答「是」，否則答「否」。天真的方法——把 N 除以直到其平方根的每個候選數——約需 N 的平方根步，而既然 N 只用約 log N 個位元寫下，這個「N 的平方根」步數對輸入大小是指數級的。所以長久以來，質數判定是否真正高效並不清楚。
里程碑式的解決出現在 2002 年，Agrawal、Kayal 與 Saxena 提出了 AKS 演算法，這是第一個確定型、無條件、多項式時間的質數判定法。它的執行時間對 N 的位數是多項式（log N 的某次方），確立了 PRIMES 屬於 P，不依賴未經證明的數論猜想，也不擲硬幣。核心想法是一個優雅的多項式恆等式：一個數 N（帶一個小技術條件）為質數，恰好當某個多項式間的同餘——大致形如 (x + a)^N 對模 N 與一個小輔助多項式同餘於 x^N + a——對足夠多的 a 值都成立時；檢查這件事可被組織成在多項式時間內執行。
PRIMES 屬於 P 之所以受到讚揚，所教的與結果本身同樣重要。它是「輸入大小指的是位數而非數值」的教科書範例，所以「試每個除數」是指數級而非線性。它也劃出一條值得記住的細線：測試 N 是否為質數屬於 P，但「分解」N（找出它的質因數）是一個不同且顯然困難得多的問題，不知是否屬於 P，而它被推定的困難性支撐著現代密碼學。知道一個數是合數，和能把它拆開，並不是同一回事。
取一個 1000 位元的數 N（約 300 個十進位數字，密碼學使用的大小）。試除法約需 N 的平方根，約 2^500 步，全然無望。AKS 在對 1000 位元為多項式的時間內判定質數性，輕而易舉。然而把同一個 N 分解成它的質因數則沒有已知的多項式演算法，這就是為什麼這樣的數能保護秘密。
試除法對位數是指數級的；AKS 是多項式，所以 PRIMES 屬於 P，而分解問題仍顯然困難。
PRIMES 屬於 P（判定質數性）和「分解容易」不是同一回事；找出質因數是一個獨立的問題，沒有已知的多項式演算法，而它被假定的困難性是許多密碼學的基礎。