素数测试
Miller-Rabin素数测试
要判断一个数$n$是否是素数，最简单的方法是遍历$2$到$\sqrt{n}$，如果其中存在$n$的因子，就意味着$n$是合数，否则就是素数。这个算法的时间复杂度为$O(\sqrt{n})$，如果$n$特别大，则不是什么好主意。
由费马小定理，可知，如果$n$是素数，对于一切$1$到$n-1$的数值$x$，都应该满足$x^{n-1}=1$。利用这个性质，我们可以过滤掉很多合数。比如$2^5=2\pmod 6$，因此可以断定$6$是合数。
但是$x^{n-1}=1$是$n$是素数的必要条件，而非充分条件。比如$8^8=1\pmod 9$，但是你不能就因此说9是素数。实际上，在$2$到$n-1$之间选择多个$x$进行测试可以大大增强结果的可信度，比如$2^8=4\pmod 9$。不幸的是，存在一类特殊的合数$c$，对于任意$1$到$c-1$之间的数$x$，都满足$x^{c-1}=1\pmod c$，这种合数称为Carmichael数，其中的一个例子就是$561$。
要处理这类Carmichael数，我们需要引入Miller Rabin算法。其原理非常简单：
\[x^2=1\rightarrow (x-1)(x+1)=0\rightarrow x=1\lor x=n-1(\pmod n)\]因此由于$n-1$为偶数，因此我们能要求$x^{\frac{n-1}{2}}$的值为$1$或$n-1$。如果$x^{\frac{n-1}{2}}=1$且$\frac{n-1}{2}$是偶数，我们可以继续使用上面过程。比如对于$n=561$。
\[2^{560}=1\pmod{561}\\ 2^{280}=1\pmod{561}\\ 2^{140}=67\pmod{561}\]因此在第三次判断时，发现$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(s\log_2n)$的。