素性测试
素性测试或素数判定，是檢驗一個給定的整數是否為質數的测试。
目录
1 素数
2 素数判定的历史
3 確定型演算法
4 隨機演算法
5 参见
6 外部链接
素数
質數是除了自身和1以外，没有其它素数因子的自然数。自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。
素数判定的历史
鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找質数公式，到了高斯时代，基本上确认了简单的質数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。
質性判斷演算法可分為兩大類，確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢，後者則反之。詳見以下列表。
確定型演算法
- 試除法﹝埃拉托斯特尼篩法﹞
- 嘗試從2displaystyle 2
到Ndisplaystyle sqrt N
的整數是否整除Ndisplaystyle N
。
- 嘗試從2displaystyle 2
/*埃拉托斯特尼篩法*/
int is_prime(int x)
if(x <= 1) return 0; /* 1不是質數，且不考慮負整數與0，故輸入 x<=1 時輸出為假 */
for(int i = 2; i * i <= x; i++)
if(x % i == 0) return 0; /* 若整除時輸出為假，否則輸出為真 */
return 1;
- 卢卡斯-莱默检验法
AKS質數測試- PRIMES is in P這篇論文提到的方法，是第一個多項式時間的質數測試演算法。
隨機演算法
费马素性检验- 利用費馬小定理來測試。
- 米勒-拉賓檢驗
- 歐拉-雅科比測試
- 對於n，挑選随机的a<ndisplaystyle a<n
，測試(an)=a(n−1)/2modndisplaystyle (a over n)=a^(n-1)/2mod n
，这里(an)displaystyle (a over n)
为雅可比符号。如果N為質數，等式一定成立；如果N為合數，等式有一半的機率不成立。
- 對於n，挑選随机的a<ndisplaystyle a<n
参见
- 素数公式
- 费马小定理
- 埃拉托斯特尼筛法
外部链接
| ||||||||||||||||||||||||||||||||||||||
