普拉特證書

普拉特證書是一種基於費馬小定理逆定理的素性證書。在普拉特（Pratt，1975）的工作之前，Lucas-Lehmer 檢驗一直被純粹視為一種在很多時候有效的啟發式方法（Knuth 1969）。普拉特（1975）表明，透過將 Lehmer 的素性啟發式方法遞迴地應用於 的因子，可以使其成為一種非確定性過程。作為這一結果的推論，普拉特（1975）成為第一個證明由此產生的樹意味著素因數分解屬於複雜度類 NP 的人。

要生成普拉特證書，假設 是一個正整數，而 是 的素因子的集合。假設存在一個整數 （稱為“證人”），使得 ，但當 是 之一時， (mod )。那麼費馬小定理逆定理指出 是素數（Wagon 1991，第 278-279 頁）。

透過將費馬小定理逆定理應用於 並遞迴地應用於 的每個聲稱的因子，可以生成給定素數的證書。換句話說，普拉特證書給出了數字 是乘法群 (mod ) 的原根的證明，這與 的階為 這一事實一起，證明了 是一個素數。

上圖給出了 素性的證書。短劃線右邊的數字是左邊數字的證人。 對於 由 給出。由於 但 , , (mod 7919)，7 是 7919 的證人。素因子 是 2、37 和 107。2 是所謂的“自證人”（即，它被認為是素數而無需進一步證明），其餘的證人顯示為巢狀樹。它們共同證明 7919 確實是素數。因為它需要 的因式分解，所以普拉特證書的方法最適合應用於小數字（或那些已知 的 易於分解的數字）。

對於小數字而言，普拉特證書的生成速度比其他型別的素性證書更快。Wolfram 語言函式ProvablePrimeQ[n] 在 Wolfram 語言包中PrimalityProving`因此，僅對於超過一定限制的數字（預設情況下為 ），才生成 Atkin-Goldwasser-Kilian-Morain 證書，而對於較小的數字則生成普拉特證書。