素性测试 - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for 素性测试.

素性测试

维基百科,自由的百科全书

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

素数

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

素数判定的历史

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

确定型算法

  • 试除法(埃拉托斯特尼筛法
    • 尝试从的整数是否整除
// 以C語言實現埃拉托斯特尼篩法
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;
}

随机算法

  • 费马素性检验
  • 米勒-拉宾检验
  • 欧拉-雅科比测试
    • 对于n,挑选随机的,测试,这里为雅可比符号。如果N为素数,等式一定成立;如果N为合数,等式有一半的概率不成立。

参见

外部链接

{{bottomLinkPreText}} {{bottomLinkText}}
素性测试
Listen to this article