產業等級質數

簡介

質數（Prime number），又稱素數，指在大於1的自然數中，除了1和該數自身外，無法被其他自然數整除的數（也可定義為只有1與該數本身兩個正因數的數）。大於1的自然數若不是素數，則稱之為合數。

產業等級質數簡單來說是指一個整數通過了素數測試但在數學上缺乏嚴格證明。產業等級質數有時會用來代替一些算法中需要的認證質數，像RSA加密算法就需要用戶產生大的質數。若數字位數超過100位，證明它們是產業等級質數會比素性測試簡單很多。前者可以立即產生，而其不是質數的失效率很低，因此在實務上幾乎不可能失效。換句話說，對於於這些數字是質數可以抱持非常高的信心，不過不是一定成立。

素數測試

素數問題是一個使得很多數學家著迷的問題。素數就是一個除了 1 和它自身以外不能被其它數整除的數。素數的一個基本問題是如何有效地確定一個數是否是一個素數，即素性測試問題。素性測試問題不僅在數學上是一個有挑戰性的問題，而且在實際中也是非常重要的。例如，很多現代密碼學套用通常需要確定一個幾百位的素數。如果不採用一些專門有效的方法，即使人們使用運行速度最快的計算機來測試一個 100 位的十進制整數，那么花費的時間將超過宇宙存在的時間。數學家嘗試設計對素數的有效測試已經長達兩千多年了。Eratosthenes篩法是對於所有素數都有效的最古老的算法，然而它的時間複雜性是輸入規模的冪指數，因此在實際中使用它是不合適的。17 世紀的 Fermat 小定理是一些有效素性測試算法的起點，但其逆定理是不滿足的。上世紀 80 年代，這個領域的普遍觀點是應該存在一個用於素性測試的確定的多項式時間算法，但沒有人能給出證明。已經確立了一些素性測試算法，但是它們都存在一些問題。一些算法是非常快速的，但是這些算法會以很小的機率產生一個錯誤結果；另一些算法是有條件的，如使用了未證明的假設；還有一些算法是確定的也是無條件的，但不能在多項式時間內完成。因此，設計一個在多項式時間內每次都給出一個正確回答的有效算法在計算機科學和數學中都是一個挑戰。多年來，研究者們已經嘗試了很多方法，包括使用了一些複雜的數學技術，但沒有一個成功。

米勒-拉賓素性檢驗

米勒-拉賓素性檢驗是一種素數判定法則，利用隨機化算法判斷一個數是合數還是可能是素數。卡內基梅隆大學的計算機系教授Gary Lee Miller首先提出了基於廣義黎曼猜想的確定性算法，由於廣義黎曼猜想並沒有被證明，其後由以色列耶路撒冷希伯來大學的Michael O. Rabin教授作出修改，提出了不依賴於該假設的隨機化算法。首先介紹一個相關的引理。