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^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, 则说明满足第二个形式，若从未得到 - 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\) 有:

\[ \begin{aligned} & ia \equiv ja(mod\ p) \\ \Rightarrow & (i-j)a = kp\ (k \in \mathbb{Z}) \\ \Rightarrow & p | (i-j)a \end{aligned} \]

由于假设，有 \(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)!\), 即得:

\[ a^{p-1} \equiv 1 (mod\ p) \]

二次探测定理:

\[ \begin{aligned} & x^2 \equiv 1(mod\ p) \\ \Rightarrow & x^2 -1 \equiv 0(mod\ p) \\ \Rightarrow & p | (x+1)(x-1) \\ \end{aligned} \]

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

\[ x \equiv 1(mod\ p) \lor x \equiv -1(mod\ p) \]