Miller-Rabin素数测试算法

用来干嘛的

要判断一个数 \(n\) 是否为素数，最朴素直接的办法是以\(O(\sqrt n)\) 时间复杂度地从2到 \(\sqrt n\) 循环即可得到最准确的结果。但是如果在 \(n\) 比较大的情况下，时间花销就太大了。这时，我们可以选择牺牲一点点准确度，使用可爱的米勒-拉宾（Miller-Rabin）素性检验算法来判断质数。根据百度百科，使用快速幂运算，这个算法的时间复杂度是 \(O(k\log^3 n)\)的，\(k\)是我们设定对一个数的进行测试的次数。\(k\) 越大，判断错误的几率越低，保守估计大概是\(4^{-k}\)，实际效果极佳，我们一般取到10就可以了。

谁搞出来的(摘自百度百科)

米勒-拉宾素性检验是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。

要用到的数学定理

费马小定理：

如果\(p\)是一个质数，而且整数\(a\)与\(p\)互质（即最小公因数\(gcd(a,p) = 1\)），则有\(a^{p-1}≡1(mod~p)\)（模\(p\)同余符号）。但是这个命题的逆命题不一定能判断一个数是否为素数，只能说明不满足\(a^{p-1}≡1(mod~p)\)条件的 \(p\) 一定是合数。在本算法里，主要就是运用了它的逆命题来检验素数的。

证明：不会，感兴趣的同学可以自己搜索相关证明（很多种），用完全剩余系的证明方法比较容易理解

二次探测定理：

若 \(n\) 为大于2的素数,则对于任意整数 \(a∈[1,n-1]\),使方程\(a^2=1(mod~n)\)成立的解有仅有\(a=1\)或者\(a=n-1\)。在算法中同样通过判断是否可以满足这个解情况，增强素数判断的准确性。

证明：还是不会，其实挺好证明的。这位博主的分析比较详细，可以看看

算法流程

首先对于一个数 \(num\),先判断是不是偶数和小于等于2这两种可以直接筛掉的情况。如果不是，那么就正式进入判断流程了。\(num\) 必为奇数，则\(num-1\)一定是个偶数，而偶数可以分解为\(2^s \cdot t = num-1\)的形式。这里如果我们让两边作为一个整数\(a\)的指数，不就可以利用费马小定理\(a^{num-1}≡1(mod~num)\)来检验 \(num\) 是否为素数了吗？别急，在算出 \(a^{2^s \cdot t}\) 的过程中，我们可以顺便利用二次探测定理来检测，大大提高我们判断的准确度。我们的做法是先随机产生一个比 \(num\) 小的整数 \(a\) ,先计算出\(a^t\) ,在我下面的代码中把这个值记作 \(x\)。然后循环 \(s\) 次，每次都用一个变量 \(test\) 记录 \(x^2\) 对 \(num\) 取模的值，如果 \(test = 1\)则说明\(x^2=1(mod~num)\)成立，进而可以判断 \(x\) 是否为1或者\(num-1\) ，如果\(x\) 都不是则说明 \(num\) 肯定不是素数啦。反复运用 \(s\) 次二次探测定理，最后再判断一次\(a^{2^s \cdot t}≡1(mod~num)\)是否成立，如果过了最后费马小定理这关，恭喜这个 \(num\) 经过了第一层考验。我们对 \(num\) 进行 \(k\) 次这样的考验，每次取一个不同的 \(a\) ,如果始终没有返回，则说明 \(num\) 最终通过了 \(Miller\) 测试。

c++代码

码风极丑警告，注释过多。需要用到快速幂和快速（也叫龟速）乘（不会的同学可以百度一下哦）。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;//miller-rabin素数检验一般应用于大数的快速检测，用long long

//快速乘，代替乘法，防止a乘b爆long long

ll qMul(ll a,ll b,ll mod){

    ll ans = 0;//a乘b等价转化为b个a相加，和快速幂原理一致

    while(b){

        if(b&1) ans = (ans+a)%mod;

        a = (a+a)%mod;

        b>>=1;

    }

    return ans;

}

//快速幂模板

ll qPow(ll base,ll power,ll mod){

    ll ans = 1;

    while(power){

        if(power&1) ans = qMul(ans,base,mod);

        base = qMul(base,base,mod);

        power>>=1;

    }

    return ans%mod;

}

//miller-rabin素数检验函数

bool Miller_Rabin(ll num){

    if(num == 2) return true;  //2为质数

    if(!(num&1)||num<2) return false;//筛掉偶数和小于2的数

    ll s = 0,t = num-1;  //流程中的s和t，2的s次方*t = num-1

    while(!(t&1)){         //当t为偶数的时候，可以继续分解

        s++;

        t>>=1;

    }

    for (int i = 1; i <= 10; i++) {    //进行十次测试即可得到比较准确的判断

        ll a = rand()%(num-1)+1;  //流程中的随机整数a，在1到num-1之间

        ll x = qPow(a,t,num);        //x为二次探测的解

        for(int j = 1;j <= s;j++){      //x平方s次可以得到a的num-1次方

            ll test = qMul(x,x,num); //test为x平方后对num取模

            if(test == 1 && x != 1 && x != num-1) return false;   //如果平方取模结果为1，但是作为解的x不是1或者num-1，说明num不是质数，返回

            x = test;

        }

        if(x != 1) return false;        //费马小定理作最后检测，a的num-1次方对num取模不等于1，一定不是质数

    }

    return true;                          //腥风血雨后仍坚持到最后，基本就是真正的质数了

}

int main(){

    ll num;

    while(cin>>num){

        if(Miller_Rabin(num)) cout<<num<<" is a prime."<<endl;

        else cout<<num<<" is not a prime."<<endl;

    }

    return 0;

}

题目

牛客NC14703素数回文

我就是看了这道题才想去学Miller-Rabin素数检测的（实际上用朴素的方法也能过），用Miller-Rabin可以比朴素的算法快十倍（如果哪一天被卡了别打我）。感兴趣的可以去做一下，搞出回文数后套Miller-Rabin算法判断即可，注意要开long long。

巴特西

Miller-Rabin素数测试算法

用来干嘛的

谁搞出来的(摘自百度百科)

要用到的数学定理

费马小定理：

二次探测定理：

算法流程

c++代码

题目

博客园第一篇博文，谢谢观看ヾ(≧▽≦)o,如果觉得有帮助请给我点个小心心 (>.<*)

最新文章

热门文章

巴特西

Miller-Rabin素数测试算法

用来干嘛的

谁搞出来的(摘自百度百科)

要用到的数学定理

费马小定理：

二次探测定理：

算法流程

c++代码

题目

博客园第一篇博文，谢谢观看ヾ(≧▽≦*)o,如果觉得有帮助请给我点个小心心 (*>.<*)

最新文章

热门文章

博客园第一篇博文，谢谢观看ヾ(≧▽≦)o,如果觉得有帮助请给我点个小心心 (>.<*)