查看“︁素性测试”︁的源代码

{{NoteTA
|G1 = Math
}}
'''素性测试'''或'''素数判定'''，是檢驗一個給定的整數是否為[[質數]]的测试。

==素数==
{{main|素数}}
[[質數]]是除了自身和[[1]]以外，没有其它素数因子的[[自然数]]。自从[[欧几里得]]证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。

==素数判定的历史==
鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找[[質数公式]]，到了高斯时代，基本上确认了简单的質数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。
質性判斷演算法可分為兩大類，確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢，後者則反之。詳見以下列表。

==確定型演算法==
* 試除法（[[埃拉托斯特尼篩法]]）
** 嘗試從 <math>2</math> 到 <math>\sqrt{N}</math> 的整數是否整除 <math>N</math>。

<syntaxhighlight lang="c">
// 以 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
}
</syntaxhighlight>

* [[威尔逊定理]]
** [[当且仅当]]<math>p</math>为質數时：
:<math>(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)</math>
* [[卢卡斯-莱默检验法]]
* [[AKS質數測試]]
** PRIMES is in P這篇論文提到的方法，是第一個多項式時間的質數測試演算法。

==[[隨機演算法]]==
* [[费马素性检验]]
** 利用[[費馬小定理]]來測試。
* [[米勒-拉賓檢驗]]
* 歐拉-雅科比測試 
** 對於n，挑選随机的<math>a<n</math>，測試<math>( {a \over n} ) = a ^ {( n - 1) / 2} \mod n</math>，这里<math>( {a \over n} )</math>为雅可比符号。如果N為質數，等式一定成立；如果N為合數，等式有一半的機率不成立。

==参见==
*[[素数公式]]
*[[费马小定理]]
*[[埃拉托斯特尼筛法]]
*[[卢卡斯-莱默检验法]]
*[[米勒-拉宾检验]]
*[[试除法]]
*[[费马素性检验]]
*[[孪生素数]]
*[[三胞胎素数]]
*[[四胞胎素数]]
*[[素数判定法则]]
*[[表兄弟素数]]
*[[六素数]]
*[[X²+1素数]]

==外部链接==

{{質數}}
{{数论算法}}

[[Category:素性测试| ]]
[[Category:非对称密钥算法]]