\(Miller-Rabin\)素数测试
用途
判断整数\(n\)是否是质数，在\(n\)较小的情况下，可以使用试除法，时间复杂度为\(O(\sqrt n)\)。但当\(n\)的值较大的时候，朴素的试除法已经不能在规定时间内解决问题。此时，我们可以用\(Miller-Rabin\)素数测试算法，时间复杂度可以降低至\(O(\log_2n)\)。
引理
费马小定理
若\(a,p \in \mathbb{Z}\)，\(p\)为质数，则
\]
在此不给出证明。
二次探测定理
描述
若\(a,p \in \mathbb{Z}\)，\(a^{2} \equiv 1(mod\;p)\)，\(p\)为质数，则\(a \equiv 1(mod\;p)\)或\(a \equiv p-1(mod\;p)\)。
证明
&\because a^{2} \equiv 1(mod\;p)\\
&\therefore p \mid (a^{2}-1)\\
&\therefore p \mid (a+1)(a-1)\\
&\because p为质数\\
&\therefore p \mid (a+1) 或(a-1)\\
&\therefore a+1 \equiv 0(mod\;p)或a-1 \equiv 0(mod\;p)\\
&\therefore a \equiv 1 (mod\;p)或a \equiv p-1 (mod\;p)\\
\end{aligned}
\]
过程
根据费马小定理，我们可以得到一个真命题：若\(p\)为质数，则\(a^{p-1} \equiv 1(mod\;p)\)。我们考虑这一命题的逆命题：若\(a^{p-1} \equiv 1\)，则\(p\)为质数。我们会惊讶地发现，这一逆命题在大多数情况下竟然成立。也就是说，我们得到了一种有效地判断质数的方法，即取一个底数\(a\)，判断它与所需判断的数\(p\)是否满足这一等式。尽管有时可能出错，但这一算法的效率相比起朴素算法来说有了很大的提升。
接下来我们要做的就是提高这一算法的正确性。首先想到的自然是取多个\(a\)值，在常见的题目中，取\([2,29]\)大概就能通过测试，当然也可以随机生成，注意\(a\)的值应该小于\(p\)。第二个优化是基于二次探测定理的。设\(p=2^nm+1\)，则可先算出\(a^m\)，然后再平方\(n\)次，求得\(a^{p-1}\)。在这一过程中，若某次平方后所得的结果为\(1\)但上次平方后的结果不等于\(p-1\)或\(1\)，就出现了矛盾，从而就不满足\(p\)为质数这一前提。最后再次判断是否满足等式即可。
注意乘法可能越界，应拆成类似快速幂的算法。
代码
const int prime[10]={2,3,5,7,11,13,17,19,23,29};
long long multi(long long a,long long b,long long p)
{
long long t=0;
while(b)
{
if(b&1)
t=(t+a)%p;
a=(a<<1)%p;
b>>=1;
}
return t;
}
long long power(long long a,long long b,long long p)
{
long long t=1;
while(b)
{
if(b&1)
t=multi(t,a,p);
a=multi(a,a,p);
b>>=1;
}
return t;
}
bool Miller_Rabin(long long x)
{
if(x==2)
return true;
if(!(x&1)||x<2)
return false;
long long t=x-1,exponent=0;
while(!(t&1))
{
t>>=1;
++exponent;
}
for(int i=0;i<10&&prime[i]<x;++i)
{
long long m=power(prime[i],t,x);
for(int j=0;j<exponent;++j)
{
long long n=multi(m,m,x);
if(n==1&&m!=1&&m!=x-1)
return false;
m=n;
}
if(m!=1)
return false;
}
return true;
}