素性測試

素性測試是一種用於確定給定數字是否為素數的測試，而不是實際將數字分解為其組成素因子（這被稱為素因數分解）。

素性測試分為兩種型別：確定性測試和機率性測試。確定性測試絕對確定地判斷一個數字是否為素數。確定性測試的例子包括盧卡斯-萊默測試和橢圓曲線素性證明。機率性測試可能（儘管機率非常小）錯誤地將合數識別為素數（但反之則不然）。然而，它們通常遠快於確定性測試。因此，通過了機率性素數測試的數字被恰當地稱為可能素數，直到它們的素性可以被確定性地證明。

一個通過了機率性測試但實際上是合數的數字被稱為偽素數。有許多特定型別的偽素數，最常見的是費馬偽素數，它們是儘管是合數但仍滿足費馬小定理的數。

拉賓-米勒強偽素數測試是一種特別有效的測試。Wolfram 語言實現了基於基數 2 和 3 的多重拉賓-米勒測試，並結合盧卡斯偽素數測試作為函式使用的素性測試PrimeQ[n]。與許多此類演算法一樣，它是一種使用偽素數的機率性測試。為了保證素性，必須使用速度慢得多的確定性演算法。然而，實際上沒有已知數字通過了高階機率性測試（如拉賓-米勒測試）但實際上是合數。

任意數字的確定性素性測試的最新技術是橢圓曲線素性證明。截至 2009 年 2 月，程式認證的最大數字PRIMO（7993 位十進位制數字）在 2-GHz 處理器上花費了八個月。

與素因數分解不同，長期以來人們認為素性測試是一個P 問題 (Wagon 1991)。然而，直到 Agrawal等人 (2002) 意外地發現了一種多項式時間素性測試演算法，其漸近複雜度為 (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002)。他們的演算法後來被稱為AKS 素性測試。