Primality Test

Primality Test

質數測試,測試一個數字是否為質數。質數測試的方法相當多,其中有保證結果一定正確的方法,亦有結果不一定正確的方法。以下所介紹的,除了Divisibiity Test的結果一定是正確的,其他方法的結果都不一定正確。

質數測試屬於P問題,不過以下介紹的皆非多項式時間的演算法,甚至是不保證結果正確的演算法。若對多項式時間、保證結果正確的演算法有興趣,可上網搜尋AKS Algorithm。

要進行質數測試,也可以直接用篩法把所有質數生出來,再來判斷質數,這也是多項式時間的解法。

Divisibility Primality Test

演算法

整除性測試法。依照質數定義,一個質數p不會被大於1且小於p的數字整除,只要把這些數字都拿來試除,就可以判定一個數字是不是質數。

撇開定義,這演算法其實就是窮舉所有可能的因數一一試除。

判斷一個數字是不是質數

時間複雜度

這個演算法會進行sqrt(n)-1次除法,可推得時間複雜度為O(sqrt(n)),然而前提是:不管n多大,每次除法都是O(1)。

加速

當要測試的數字很多時,可先建立質數表,進行質數測試時僅檢查質因數。

Fermat's Primality Test

費馬小定理

若n是質數,則a^(n-1) ≡ 1 (mod n)。

演算法

費瑪質數測試法是運用費瑪小定理而想出的方法:

若n是質數,則費瑪小定理一定成立:a^(n-1) % n = 1一定成立。
若n是合數,則費瑪小定理不一定成立:a^(n-1) % n = 1有可能會成立。

當a^(n-1) % n = 1成立的時候就說n是質數。

這個演算法的結果不一定正確,有些合數也許會被判定成質數。但只要使用各式各樣的a來進行測試,那麼結果就會更加準確。

測試一個數是否為質數

Square Root Primality Test

演算法

若n是質數,則1~n之間,只有1與n-1,其平方後模n會餘1。
若n是合數,則可能還會有其它的數字,其平方後模n會餘1。

(若以質數n為模,1的平方根只會等於±1,不會等於其他數。
 若以合數n為模,1的平方根只會等於±1,還可能會等於其他數。)

如果2~n-1的數字,其平方後模n都不餘1,就說n是質數。

這個演算法的結果不一定正確,有些合數也許會被判定成質數,例如22就會判定成質數,2^2、3^2、…、21^2模22後剛好都餘1。

測試一個數是否為質數

Miller-Rabin Primality Test

演算法

這是結合Fermat's Primality Test與Square Root Primality Test的一個方法。這個演算法的結果不一定正確,有些合數也許會被判定成質數。

1. 選定一個底數a,用來進行費馬測試。
2. 把n-1拆解成m * 2^k的形式,m為奇數。
3. 觀察a^m模n。若為±1,
   則表示n最後可以通過費馬測試,接下來也不再出現平方根測試的反例。
   推定n為質數。
4. 依序觀察a^m、(a^m)^2 = a^(m * 2^1)、((a^m)^2)^2 = a^(m * 2^2)
   、…、((((a^m)^2)^2)…^2) = a^(m * 2^(k-1))這些數字:
  甲、一旦發現有個數字平方後模n餘+1,
    則表示n無法通過平方根測試。
    推定n為合數。
  乙、一旦發現有個數字平方後模n餘-1,
    則表示n最後可以通過費馬測試,接下來也不再出現平方根測試的反例。
    推定n為質數。
5. 最後無法判定結果。推定n為合數。

測試一個數是否為質數

步驟零。當t為±1:甲、t接下來的值會一直等於+1,於最後一步驟算式中可發現n通過費馬測試。乙、t接下來的值會一直等於1,我們不會檢查到違反平方根測試的情況。由甲乙兩點,推定n為質數。

步驟一到步驟k-1。一、當t為+1:n會通過費馬測試法,原理同前;但是n不會通過平方根測試法,因為上一個步驟的t不會是±1,而它的平方再模n(也就是此步驟的t)竟然等於1,也就是說我們發現了平方根測試的反例,故n必是合數。二、當t為-1:同步驟零的甲乙兩點,推定n是質數。三、若t為其他值:則無法判定n是質數或合數,繼續執行演算法。

步驟k。仍無法判定n是質數或是合數,故推定n為合數。