素数测试

Published: by Creative Commons Licence

  • Tags:

Miller-Rabin素数测试

要判断一个数n是否是素数，最简单的方法是遍历2到√n，如果其中存在n的因子，就意味着n是合数，否则就是素数。这个算法的时间复杂度为O(√n)，如果n特别大，则不是什么好主意。

由费马小定理，可知，如果n是素数，对于一切1到n−1的数值x，都应该满足xn−1=1。利用这个性质，我们可以过滤掉很多合数。比如25=2(mod6)，因此可以断定6是合数。

但是xn−1=1是n是素数的必要条件，而非充分条件。比如88=1(mod9)，但是你不能就因此说9是素数。实际上，在2到n−1之间选择多个x进行测试可以大大增强结果的可信度，比如28=4(mod9)。不幸的是，存在一类特殊的合数c，对于任意1到c−1之间的数x，都满足xc−1=1(modc)，这种合数称为Carmichael数，其中的一个例子就是561。

要处理这类Carmichael数，我们需要引入Miller Rabin算法。其原理非常简单：

x2=1→(x−1)(x+1)=0→x=1∨x=n−1((modn))

因此由于n−1为偶数，因此我们能要求xn−12的值为1或n−1。如果xn−12=1且n−12是偶数，我们可以继续使用上面过程。比如对于n=561。

2560=1(mod561)2280=1(mod561)2140=67(mod561)

因此在第三次判断时，发现561不满足素数的要求。这样我们就解决了Carmichael数。

如果你随机从1到n−1中抽取x来印证一个奇数n是素数，重复上面过程s次，那么Miller Rabin出错的概率至多为2−s，详细内容见《算法导论》。

boolean mr(int n, int s)
{
    if(n == 2)
    {
        return true;
    }
    if(n % 2 == 0)
    {
        return false;
    }
    for(int i = 0; i < s; i++)
    {
        int x = RANDOM(2, n - 1);
        if(!mr0(x, p))
        {
            return false;
        }
    }
    return true;
}

boolean mr0(int x, int n)
{
    int exp = n - 1;
    while(true){
        int y = pow(x, exp) % n;
        if(y != 1 && y != n - 1)
        {
            return false;
        }
        if(y != 1 || exp % 2 == 1)
        {
            break;
        }
        exp = exp / 2;
    }
    return true;
}

注意上面的代码并没有进行优化，Miller Rabin的代码其实可以优化到O(slog2n)的。