頭條新聞

素性測試變得容易

作者：Eric W. Weisstein

2002 年 8 月 7 日——素數是指除了 1 和自身之外沒有其他整數因數的整數。例如，6 不是 素數，因為它除了 1 和 6 之外還有因數 2 和 3。另一方面，7 是 素數，因為它的因數只有 1 和 7。不是素數的數字稱為合數。

雖然素數簡單易於描述和理解，但儘管自歐幾里得和埃拉託斯特尼時代以來，它們一直是深入數學研究的主題，但素數的性質卻出乎意料地難以捉摸。雖然歐幾里得證明了存在無限多個素數（這個結果現在被稱為歐幾里得第二定理，出現在歐幾里得著名的幾何原本命題 IX.20 中），但確定一個給定的數字是素數還是合數，更不用說將其分解為所謂的素因數分解（如果是合數）已被證明是一個難題。由於素數在RSA 演算法等加密演算法中的廣泛應用，這個問題近年來受到了極大的關注。例如，如果存在分解大數的有效演算法，那麼全球絕大多數加密電子通訊將很容易被破解。

演算法複雜度理論是一門數學學科，它根據問題求解的難度對問題進行分類。如果解決問題所需的步驟數受到問題規模的某個冪的限制，則該問題被分配到 P 類（其中“P”代表“多項式時間”）。如果一個問題允許非確定性解法，並且驗證解法所需的步驟數受到問題規模的某個冪的限制，則該問題被分配到 NP 類（其中“NP”代表“非確定性多項式時間”）。素性測試（換句話說，在不實際計算任何因數的情況下確定一個數字是否為素數）比素因數分解更容易，並且長期以來一直被認為是 P 類問題。

今天已知的最有效的素因數分解和素性測試演算法是機率性的，因為它們使用複雜的技術，幾乎總是返回結果，但並非以絕對的數學確定性這樣做。例如，Mathematica 的 PrimeQ 命令使用一種特別有效的機率演算法，稱為 Rabin-Miller 強偽素數測試來測試素性。

8 月 6 日，印度坎普爾印度理工學院的 M. Agrawal、N. Kayal 和 N. Saxena 釋出了一份電子預印本，其中包含一種據稱可以在多項式時間內測試素性的演算法 (Agrawal et al. 2002)。該論文此前已分發給許多著名的數論學家。領先專家 Hendrik Lenstra（加州大學伯克利分校）和 Carl Pomerance（貝爾實驗室）已經對該論文發表了評論，稱其結果是正確的、巧妙的和優雅的（Clark 2002, Pomerance 2002）。雖然該演算法的漸近時間複雜度已被證明對於整數 n 為 O(ln¹²n)（這意味著執行時間與被測數字的自然對數的 12 次方成正比），但啟發式方法表明，在實踐中，該演算法的時間複雜度為 O(ln⁶n)，如果可以證明另一個數論猜想，則可以進一步降低到 O(ln³n)。

更快的素性測試不會對電子通訊的安全性構成任何直接風險。然而，它確實為大大加快數論許多領域的數學計算開闢了可能性。現在斷言新演算法是否可以以能夠與快速機率方法競爭的方式實現還為時過早。但是，作為一種權威地區分可能素數（根據某些測試或測試集看起來是素數，但無法嚴格確定其素數的素數）與實際素數的方法，它可能已經是目前最快的演算法之一！