Miller-Rabin素数判定

发表于 | 分类于 ，

概述:

Miller-Rabin素数判定算法主要通过下面的两个定理实现素数探测:

  • 费马小定理: 若$p$为素数, 则$a^{p-1} \equiv 1 (mod\ p)$

  • 二次探测定理: 若$p$为素数, 且$x^{2} \equiv 1 (mod\ p)$, 则$x \equiv 1(mod\ p)$或$x \equiv -1(mod\ p)$

假设只使用费马小定理判定素数, 即任取$a < p$, 计算$a^{p-1}$, 若$a^{p-1}(mod\ p) \neq 1$, 则说明$p$一定不是素数, 若进行多次判定$a^{p-1} \equiv 1(mod\ p)$均成立, 则可以认为$p$是素数.

但是只使用费马小定理判定素数将会出现卡米歇尔数, 即存在合数$n$, 对于所有满足$a < n$且$gcd(a,n)=1$的数都有$a^{n-1} \equiv 1(mod\ p)$, 这将导致费马素性测试变得不够可靠.

实现:

根据上面的两个定理, 假设$n$是个素数, 且$n > 2$, 则$n-1$是偶数, 可以表示为$2^{s} \times d$, 其中$d$为奇数. 则对于任意的小于n的正整数$a$和$0 \leq r \leq s-1$, 必满足下面两种形式的其中一种:

因为根据费马小定理, 有:

又由于二次探测定理, 如果我们对$a^{n-1}$不断取平方根, 总会取得1或-1. 如果中间得到了一个-1, 则说明满足第二个形式, 若从未得到-1, 则说明满足第一个形式.

Miller-Rabin素数判定便是基于上述原理的逆否, 即对于一个大于2的奇数$n$, 存在正整数$a<n$, 不符合上述形式, 则其一定不是素数. 否则$n$可能是一个素数. 如果选取多个$a$均符合上面两种形式的其中一种, 则说明$n$大概率是素数.

说是概率性判断但准确率其实很高, 对于$2^{32}$以内的数据只需要选取2,7,61三个数即可做到正确判断.

时间复杂度为$O(klog^2n)$, 其中k为选取的判断数的个数.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef long long LL;
LL fast_mod(LL a,LL p,LL m) {   //快速幂
    LL ret(1),tmp(a%m);
    for(int i(0);(1ll<<i)<=p;++i) {
        if(p&(1ll<<i)) {
            ret = (ret*tmp) % m;
        }
        tmp = (tmp*tmp) % m;
    }
    return ret;
}

LL witness[7] = {2,3,5,7,11,61,24251};  //判断数
bool millerRabin(LL x) {
    if(x==1 || (x>2 && x%2==0)) {   //偶数和1直接判断
        return false;
    } else if(x==2 || x==3 || x==5 || x==7 || x==11 || x==61 || x==24251) { //判断数本身特殊判定
        return true;
    }
    for(int k(0);k<7;++k) {
        LL rd = x-1;
        while(rd) {
            LL chk = fast_mod(witness[k],rd,x);
            if(chk!=1 && chk!=x-1) {    //如果不符合两种形式
                return false;
            }
            if(rd%2==1 || chk==x-1) {   //符合其中一种形式
                break;
            }
            rd /= 2;    //不断开方
        }
    }
    return true;
}

证明:

费马小定理:

首先证明引理: 集合$\{1,2,…,p-1\}$与集合$\{a,2a,…,(p-1)a\}$在模$p$意义下等价.

证明这个引理首先要证明对于所有正整数$x<p$, 都有$p \nmid xa$.

原因很简单, $a<p , x<p$, 意味着$xa$不可能有质因数$p$, 也就$p \nmid xa$.

然后使用反证法, 假设对于正整数$i, j < p$, 且$i > j$ 有:

由于假设, 有$0 \leq (i-j) < p$, 又由于前面的证明, $i-j=0 \iff i=j$, 与假设矛盾. 所以集合$\{a,2a,…,(p-1)a\}$在模$p$意义下有$p-1$个值, 也即$\{1,2,…,p-1\}$.

接下来证明费马小定理.

由于上述引理, 于是有:

由于$((p-1)!,p)=1$, 同余式两边可约去$(p-1)!$, 即得:

二次探测定理:

因为$p$为质数, 所以要达到上述要求$p|(x+1)$和$p|(x-1)$两者必有其一, 也即: