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

作者: wjyyy 分类: 学习笔记,数学,筛素数 发布时间: 2018-08-27 20:11

点击量:27

 

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

 

一、来源

    Miller-Rabin是由Miller和Rabin两个人根据费马小定理的逆定理,也就是费马测试优化过来的。费马小定理就是$$a^{p-1}\equiv 1(\mod p)$$

 

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

 

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

 

    我不会证谁来证一下

 

二、二次探测定理

    有一个叫二次探测定理的东西,可以有效地提升费马小定理的正确性。如果对于素数\(p\),有正整数\(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就是一个不错的选择。

 

五、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;
}

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【miller-rabin素性测试学习笔记】 […]

/* */