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;
}
02-01 13:04