素性测试

素性测试或素数判定，是检验一个给定的整数是否为质数的测试。

素数

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

素数判定的历史

鉴别一个自然数是素数还是合数，这个问题在中世纪就引起人们注意，当时人们试图寻找质数公式，到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。从此以后，这个问题吸引了大批数学家。质性判断算法可分为两大类，确定性算法及随机算法。前者可给出确定的结果但通常较慢，后者则反之。详见以下列表。

确定型算法

试除法（埃拉托斯特尼筛法）
- 尝试从 $2$ 到 ${\sqrt {N}}$ 的整数是否整除 $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
}

威尔逊定理
- 当且仅当 $p$ 为质数时：

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

卢卡斯-莱默检验法
AKS质数测试
- PRIMES is in P这篇论文提到的方法，是第一个多项式时间的质数测试算法。

随机算法

费马素性检验
- 利用费马小定理来测试。
米勒-拉宾检验
欧拉-雅科比测试
- 对于n，挑选随机的 $a<n$ ，测试 $({a \over n})=a^{(n-1)/2}\mod n$ ，这里 $({a \over n})$ 为雅可比符号。如果N为质数，等式一定成立；如果N为合数，等式有一半的几率不成立。

参见

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.