素性测试

素性测试或素数判定，是檢驗一個給定的整數是否為質數的测试。

質數是除了自身和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素数