Miller-Rabin算法

Miller-Rabin算法

欧拉定理：a,p是正整数，$ gcd(a,p)=1 $,则 $a^{varphi(p)} equiv 1 (mod p) $?

费马小定理： 假如a是正整数、p是质数，且 $ gcd(a,p)=1 $，那么 $ a^{(p-1)} equiv 1（mod p）$,即：?$ a^p equiv p（mod p）$。

对于任意素数 $p$，以及对于模p的剩余类环${1,2,...,p-1} $中的任意数 $x$，都满足$x^p equiv x(mod p) $。换句话说，$exists x$ 使得 $x^p equiv x(mod p) $不成立，$p$就不是素数。

因此我们可以用这个小小的技巧来排除大量的合数。

但是：p是素数是x^p=x(mod p)的充分条件，而非必要条件。

Carmichael数：存在一类极端的合数$p$，使得所有满足$gcd(x,p)=1$的$x$，都满足$x^p equiv x(mod p) $，例如561,1105,1729。

由于这类数的存在，使我们用费马小定理完全无法正确断定一个数是不是素数。

?二次探测定理: $ 1^2 mod p $和 $ (-1)^2 mod p $总是得到$ 1 $，称这两个数为$ 1 $的“平凡平方根”。当$ p $是素数且$ p>2 $时，不存在$ 1 mod p $的“非完全平方根”。

证明：假设$ x,x<p$是$ 1 mod p $的平方根，于是有

$$ x^2 equiv 1 (mod p) $$

$$ (x+1)(x-1) equiv 0 (mod p) $$

推出：$ p | (x+1)(x-1) $ 即 $ p | (x+1) 或 p | (x-1) $ 即 $ x=p-1 或 x=1 $ 其中 $ p-1 equiv -1 (mod p) $

证毕。

引理：

?假设一个奇素数$n,n>2$,$n-1$ 是一个偶数，可以表示为$2^s*d$的形势，$s$,$d$都是正整数且$d$是奇数。对任意在${(Z/nZ)}^*$范围内的$a$ 和 $[0,s)$范围内的$r$，必满足以下形式的一种：

$$ a^d equiv 1 (mod n) $$

$$ a^{2^r d} equiv -1 (mod n) $$

证明：

由于费马小定理：$ a^{n-1} equiv 1 (mod n ) $?

对$ a^{n-1} $不断取平方根，由二次探测定理，最后会得到$1$或$-1$。

如果得到$-1$,则$2式$成立；如果从未得到$-1$,且不能继续开平方，则$1式$成立。

证毕。

Miller-Rabin素数测试基于上述定理的逆否：如果我们找的到一个$a$,使得对于$[0,s)$范围内的$r$,

$$ a^d equiv 1 (mod n) $$

$$ a^{2^r d} equiv -1 (mod n) $$

均不满足，则$n$不是素数，这样$a$称为$n$是合数的一个凭证，否则，$a$可能是$n$是素数的强伪证。

模板：

考虑到爆 longlong，添加了快速加的操作。

#include <ctime>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long LL;
LL ksc(LL a,LL n,LL mod){
    LL ret=0;
    for(;n;n>>=1){
        if(n&1)(ret+=a)%=mod;
        (a<<=1)%=mod;
    }
    return ret;    
}
LL ksm(LL a,LL mod){
    LL ret = 1;
    for(;n;n>>=1){
        if(n&1)ret=ksc(ret,a,mod);
        a=ksc(a,mod);
    }
    return ret;
}
int millerRabin(LL n){
    if(n<2 || (n!=2 && !(n&1)))return 0;
    LL d=n-1;for(;!(d&1);d>>=1);
    for(int i=0;i<20;++i){
        LL a=rand()%(n-1)+1;
        LL t=d,m=ksm(a,d,n);
        for(;t!=n-1 && m!=1 && m!=n-1;m=ksc(m,m,n),t<<=1);
        if(m!=n-1 &&m!=1) return 0;
    }
    return 1;
}
int main(){
    srand(time(0));
    int T;scanf("%d",&T);
    for(LL n;T--;){
        scanf("%lld",&n);
        puts(millerRabin(n)?"Yes":"No");
    }
    return 0;
}

?

引用：

https://baike.baidu.com/item/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E7%B4%A0%E6%80%A7%E6%A3%80%E9%AA%8C/22719763?fromtitle=Miller%20Rabin%E7%AE%97%E6%B3%95&fromid=7918305

https://www.cnblogs.com/dalt/p/8436883.html

http://www.matrix67.com/blog/archives/234