素性测试或素数判定，是檢驗一個給定的整數是否為質數的测试。
素数
質數是除了自身和1以外，没有其它素数因子的自然数。自从欧几里得证明了有无穷个素数以后，人们就企图寻找一个可以构造所有素数的公式，寻找判定一个自然数是不是素数的方法。因为素数的地位非常重要。
素数判定的历史
鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找質数公式，到了高斯时代，基本上确认了简单的質数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。
質性判斷演算法可分為兩大類，確定性演算法及隨機演算法。前者可給出確定的結果但通常較慢，後者則反之。詳見以下列表。
確定型演算法
- 試除法
*愛拉托散尼篩
- 威尔逊定理
** 当且仅当p为質數时：
:(p-1)!\ \equiv\ -1\ (\mbox{mod}\ p)
- 卢卡斯-莱默检验法
- AKS質數測試
** PRIMES is in P這篇論文提到的方法，是第一個多項式時間的質數測試演算法。
隨機演算法
- 费马素性检验
** 利用費馬小定理來測試。
- 米勒-拉賓檢驗
- 歐拉-雅科比測試
** 對於n，挑選随机的a，測試( {a \over n} ) = a ^ {( n - 1) / 2} \mod n，这里( {a \over n} )为雅可比符号。如果N為質數，等式一定成立；如果N為合數，等式有一半的機率不成立。
参见
*素数公式
*费马小定理
*埃拉托斯特尼筛法
*卢卡斯-莱默检验法
*米勒-拉宾检验
*试除法
*费马素性检验
外部链接
评论 (0)