Miller-Rabin素性测试 学习笔记【数学】【筛素数】

点击量：252

Miller-Rabin是一种高效的随机算法，用来检测一个数$ p$是否是素数，最坏时间复杂度为$\log^3 p$，正确率约为$1-4^{-k}$，$k$是检验次数。

一、来源

Miller-Rabin是由Miller和Rabin两个人根据费马小定理的逆定理，也就是费马测试优化过来的。费马小定理就是

$$a^{p-1}\equiv 1\pmod p$$

我们知道当 $p$ 为素数时费马小定理才成立，但是如果一个数满足费马小定理，它一定是素数吗？可以发现，当这个数肥肠小时，它是满足的，但是有一天 $341$ 这个数满足以 $2$ 为底的费马小定理，满足 $2^{340}\equiv 1(\mod 341)$，但是它是合数 $(341=11\times 31)$。

这时，Miller和Rabin就改进了这个叫费马测试的东西……

我不会证谁来证一下

二、二次探测定理

有一个叫二次探测定理的东西，可以有效地提升费马小定理的正确性。如果对于素数 $p$，有正整数 $x(x<p)$ 且 $x^2\equiv 1(\mod p)$；可以推得 $x^2-1\equiv 0(\mod p)\Rightarrow p|x^2-1\Rightarrow p|(x-1)(x+1)$，而 $ x<p$，所以如果 $p|(x-1)$ 的话，$x-1=0,x=1$，或 $p|x+1$，则 $x=p-1$。因此，就有了 Miller-Rabin 测试。

三、Miller-Rabin素性测试

有了二次探测定理，我们试着进行 $341$ 的以 $2$ 为底的费马测试。$2^{340}\equiv 1(\mod 341)$，如果 $341$ 是素数，那么也满足二次探测定理，也就是 $2^{170}\equiv 1(\mod 341)$。而170还是个偶数，可以继续进行二次探测定理。这时它就凉了，因为$2^{85}\equiv 32(\mod 341)$，因为它没有通过二次探测定理，所以 $341$ 不是个素数。

同时，因为费马小定理没有要求底为什么，所以只以 $2$ 为底肯定会放过一些漏网之鱼，我们应该多选一些数为底，这样才能使判断的正确性提高。不过这个底最好选择素数（不知道为什么，可能与答案的模数大都为质数一样吧…），来保证正确性。同时，在学习这个算法时，网上会有一写神奇的结论，比如选 $3$ 个特定的底 $2,7,61$，就可以通过小于 $4,759,123,141$ 的所有素数的测试，而选 $2,3$ 为底，可以通过 $1,373,653$ 以内的测试。因此很多人都喜欢随机几个数作为底，而题目给出的质数也不一样，这就是靠碰运气了。不过上面分析过，它的错误率只有约 $4^{-k}$，所以出题人在不知道你的底数的情况下，正确率是特别高的。

上面的费马测试+二次探测就是 Miller-Rabin 了。实际检测过程是对于被测数 $n$ 而言，分解$n-1=d\cdot 2^r$。

因为 $n-1$ 要作为指数，且一直要进行二次探测，因此我们在做素性测试时要把它的因子2全部除尽，也就是上面式子的 $r$ 递减到 $0$。在除的过程中，如果出现了 $a^{d\cdot 2^{r-i}}\not\equiv 1 \ or\ n-1$ 的情况，就说明这是个合数，它没有通过 Miller-Rabin 测试。还要注意，如果 $a^{d\cdot 2^{r-i}}\equiv n-1)$，就不能继续二次探测了，因为它不满足费马小定理。但是它满足二次探测，所以它是质数的可能性不能排除。因此每次做二次探测直到余数不为 $1$。

四、总结

Miller-Rabin是肥肠高效的，写起来也比较方便。而题目中远没有变态到让你线筛出 $10^7$ 个数来，有很多包括空间在内的资源都浪费了，尤其是在卡空间的题中。这时候Milller-Rabin就是一个不错的选择。

另外，如果一个题让你筛数量规模比较小，但是数字规模比较大的数，可以考虑 Miller-Rabin。（见 「十二省联考 2019」骗分过样例）

五、Code

(luogu 线性筛模板)

因为这里的范围是 $10^7$，所以用上面的特定底数 $2,7,61$ 是可以通过的。

#include<cstdio>
#include<cstring>
long long qpow(long long x,long long y,long long p)//快速幂及模数
{
    long long ans=1,m=x;
    while(y)
    {
        if(y&1)
            ans*=m;
        ans%=p;
        m*=m;
        m%=p;
        y>>=1;
    }
    return ans;
}
bool check(long long x,long long y,long long p)//二次探测
{
    long long tmp=qpow(x,y,p);
    if(tmp!=1&&tmp!=p-1)
        return false;
    if(tmp==p-1)
        return true;
    if(tmp==1&&(y&1))
        return true;
    return check(x,y>>1,p);
}
bool millerrabin(long long x)
{
    if(x<=1)
        return false;
    if(x==2||x==7||x==61||(check(2,x-1,x)&&check(7,x-1,x)&&check(61,x-1,x)))//注意判断到自己会挂掉，我们已经知道他们是素数了就不管了qwq
        return true;
    return false;
}
int main()
{
    int n,m;
    long long u;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%lld",&u);
        if(millerrabin(u))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}