質數測試

質數測試或質數判定，是檢驗一個給定的整數是否為質數的測試。

質數

主條目：質數

質數是除了自身和1以外，沒有其它質數因子的自然數。自從歐幾里得證明了有無窮個質數以後，人們就企圖尋找一個可以構造所有質數的公式，尋找判定一個自然數是不是質數的方法。因為質數的地位非常重要。

質數判定的歷史

鑑別一個自然數是質數還是合數，這個問題在中世紀就引起人們注意，當時人們試圖尋找質數公式，到了高斯時代，基本上確認了簡單的質數公式是不存在的，因此，高斯認為對質性判定是一個相當困難的問題。從此以後，這個問題吸引了大批數學家。 質性判斷演算法可分為兩大類，確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢，後者則反之。詳見以下列表。

確定型演算法

• 試除法（愛拉托散尼篩法）
  • 嘗試從 ${\displaystyle 2}$ 到 ${\displaystyle {\sqrt {N}}}$ 的整數是否整除 ${\displaystyle N}$。

// 以 C 語言實現埃拉托斯特尼篩法
// 用以判斷質數的 is_prime 副函式
int is_prime(int x)
{
    if(x < 2) return 0;            // 1 不是質數，且不考慮負整數與 0，故輸入 x<=1 時回傳 0
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0) return 0;    // 一旦出現整除，回傳 0
    return 1;                       // 迴圈跑完後都沒有整除，回傳 1
}

• 威爾遜定理
  • 當且僅當${\displaystyle p}$為質數時：

${\displaystyle (p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)}$

• 盧卡斯-萊默檢驗法
• AKS質數測試
  • PRIMES is in P這篇論文提到的方法，是第一個多項式時間的質數測試演算法。

隨機演算法

• 費馬質性檢驗
  • 利用費馬小定理來測試。
• 米勒-拉賓檢驗
• 歐拉-雅科比測試
  • 對於n，挑選隨機的${\displaystyle a<n}$，測試${\displaystyle ({a \over n})=a^{(n-1)/2}\mod n}$，這裏${\displaystyle ({a \over n})}$為雅可比符號。如果N為質數，等式一定成立；如果N為合數，等式有一半的概率不成立。

參見

• 質數公式
• 費馬小定理
• 愛拉托散尼篩法
• 盧卡斯-萊默檢驗法
• 米勒-拉賓檢驗
• 試除法
• 費馬質性檢驗
• 孿生質數
• 三胞胎質數
• 四胞胎質數
• 質數判定法則
• 表兄弟質數
• 六質數
• X²+1質數

外部連結