Miller_Rabin

Miller_Rabin

Part0 前言：

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

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

Part1 费马小定理：

关于这个定理没什么好多讲的。

[若p是素数,则 a^pequiv amod p ]

Part2 二次探测定理：

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

定理的证明直接移项即可。

[ a^2equiv 1mod p\ herefore (a-1)(a+1)equiv0mod p\ herefore pmid (a-1)(a+1)\ ecause p是素数 (不是素数不能继续向下！)\ herefore pmid a-1 or pmid a+1\ 即 aequiv1 or aequiv a-1 (mod p) ]

Part3 Miller_Rabin:

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

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

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

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

​ 由费马小定理显然有$ a^{x-1}equiv 1mod 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;
}