Miller_Rabin

Miller_Rabin

Part0 前言：

Miller_Rabin是一个高效判定素数的随机算法。

其运用到的理论知识是：费马小定理 \(and\) 二次探测定理。

Part1 费马小定理：

关于这个定理没什么好多讲的。
\[若p是素数,则\ \ a^p\equiv p\mod p\]

Part2 二次探测定理：

\[若a^2\equiv 1\mod p\ 且p是素数\\则a\equiv1\ or\ a\equiv p-1\ (mod\ p)\]

定理的证明直接移项即可。
\[\ \ a^2\equiv 1\mod p\\\therefore (a-1)(a+1)\equiv0\mod p\\\therefore p\mid (a-1)(a+1)\\\because p是素数\ (不是素数不能继续向下！)\\\therefore p\mid a-1 \ or \ p\mid a+1\\即\ a\equiv1\ or \ a\equiv a-1\ (mod\ p)\]

Part3 Miller_Rabin:

假设当前需要判定的数是x。

一、那么若x为质数那么需要满足费马小定理。

​ 满足费马小定理只是x为素数的一个必要条件。如果连费马小定理都无法满足，必然不可能是素数。

二、但是上述条件并不充分。所以需要利用二次探测定理来进行再判断。

​ 由费马小定理显然有$  a^{x-1}\equiv 1\mod x$。

​ 又由二次探测定理有：

​ 若\(2 \mid x-1\)，则\(a^{\frac{x-1}{2}}\equiv 1\ or \ a^{\frac{x-1}{2}}\equiv x-1\)。

​ 若不满足二者中任意一个,则说明不是素数。

​ 若满足\(a^{\frac{x-1}{2}}\equiv 1\)，则可以继续二次探测。

​ 若满足\(a^{\frac{x-1}{2}}\equiv x-1\)，则无法继续探测，认定x为素数。

​ 若不满足\(2 \mid x-1\)，无法继续探测，认定x为素数。

这就是Miller_Rabin的全部过程。

事实上仍然存在很少一部分强伪素数无法被Miller_Rabin判掉。

我们可以通过多选几个数来多次判定，使这样的情况发生的概率尽可能小就好了，算法的随机就体现在这里了。

Part4 代码实现：

在代码实现过程中，若直接模拟上述流程，每一次除以2后，都需要求一个快速幂，计算次数较多。

而如果提前把所有能提出的2都先提出来，反向模拟这一过程，就只需要不断乘上自己就好了。程序会跑的更快！

IL int Miller_Rabin(int x) {
    if(x<2) return 0;
    if(x==2||x==3||x==5||x==7) return 1;
    RG int i,j,k=x-1,cnt=0,now;
    while(!(k&1)) k>>=1,++cnt;
    //先把所有的2给提出来，然后在一个一个乘上去，这样比直接做快
    for(i=1;i<=4;++i) {
        if(Pow(prm[i],x-1,x)!=1) return 0; //费马小定理
        now=Pow(prm[i],k,x);
        if(now==1||now==x-1) continue;
        now=now*now%x;
        for(j=1;j<=cnt;++j,now=now*now%x)
            if(now==x-1) break;
        if(j>cnt) return 0;
    }
    return 1;
}