定义

Miller-Rabin素数测试，又称米勒-拉宾素性检验，是一种素数判定法则，利用随机化算法判断一个数是合数还是可能是素数。
卡内基梅隆大学的计算机系教授Gary Lee Miller首先提出了基于广义黎曼猜想的确定性算法，由于广义黎曼猜想并没有被证明，其后由以色列耶路撒冷希伯来大学的Michael O. Rabin教授作出修改，提出了不依赖于该假设的随机化算法。（摘自百度百科）

用处&背景

根据上面的定义可以显然的看到，这个算法的主要目的就是进行单个素数的判定
在前期学习当中，我们也学习过单个素数的判定
复杂度为(O(sqrt n))，代码如下

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = int(sqrt(x+0.5)); i >= 2; --i) {
        if (x % i == 0) return false;
    }
    return true;
}

那么利用Miller-Rabin（简称MR）算法
还有优秀的龟速乘（快速加）以及快速幂
复杂度可以达到(O(klog_n))
MR的复杂度在百科中给出了一大堆(log)像这样：
使用快速傅里叶变换能够将这个时间推进到(O(klog_nloglog_nlogloglog_n)=O(klog_n))
总之复杂度就是(O(klog_n))

而且正确性也有一定的保障
经过证明（我不会）
每次检测MR给出的错误结果的概率小于等于(frac 1 4)
那么进行k次检测的错误概率可降低至(O({frac 1 4}^k))
实际使用效果要比理论值好不少
可以说是相当优秀了

证明

下面来看正确性的证明
需要用到的前置知识：费马小定理，二次探测定理，Wilson定理。
不太好解释，没关系，我们一个一个来看
有个别不懂的算法可以直接点击右侧目录去看

费马小定理

性质

若a，p互质，则(a^{p-1}≡1(mod p))

证明

考虑(1,2,3...(p - 1))共(p-1)个数字，给所有数字同时乘(a)，得到(a,2a,3a,...(p - 1)a)

[ecause a eq b (mod p), (c, p) = 1 ]

[ herefore ac eq bc(mod p) ]

[ herefore 1*2*3...(p - 1) equiv a*2a*3a...(p-1)a (mod p) ]

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

[ecause ((p-1)!, p) equiv 1 ]

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

二次探测定理

性质

如果(p)是一个素数，且(0<x<p)，则方程(x^2 equiv 1(mod p))的解为(x = 1, x = p - 1)

证明

[ecause x^2 - 1 equiv 0(mod p) ]

[ herefore (x + 1)(x - 1) equiv 0(mod p) ]

[ herefore p|(x -1)(x + 1) ]

[ecause x < p ]

[ herefore x = 1, x =p -1 ]

Wilson定理

性质

在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。
即：当且仅当p为素数时：(( p -1 )! ≡ -1 ( mod p ))
由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大，但借助计算机的运算能力有广泛的应用，也可以辅助数学推导。

证明

由二次探测定理，(1*(p - 1) equiv 1(modp))
在质数p的完全剩余系当中
一定存在((a, y) equiv 1(mod p))
根据欧几里得（(Euclid)）或者逆元的性质能得到
（实在不想证明了，以前讲过，算显然吧）
那么在((2,p-2))共计(p-3)个元素中
一共能够找到(frac {p - 3} 2)个这样的二元组
且都同余1
现在只剩下了1和p-1两个元素
显然两者相乘与p同余-1
则命题得证
当且仅当p为素数时：(( p -1 )! ≡ -1 ( mod p ))

至此全部的前置知识的证明已经结束，下面就是和代码实现有关的部分

实现过程

对于偶数和 0，1，2 可以直接判断。
设要测试的数为 x，我们取一个较小的质数 a，设 s,t，满足 (2^scdot t=x-1)（其中 t 是奇数）。
先求出 (a^t)，然后不断地平方并且进行二次探测（进行 s 次）。
最后我们根据费马小定律，如果最后 (a^{x-1} otequiv 1(mod :\, x))，则说明 (x) 为合数。
多次取不同的 (a) 进行多次 (Miller : Rabin) 素数测试，这样可以使正确性更高

备注

我们可以多选择几个 (a)，如果全部通过，那么 (x) 大概率是质数。
(Miller : Rabin) 素数测试中，“大概率”意味着概率非常大，基本上可以放心使用。
当 (a) 取遍小等于 (30) 的所有素数时，可以证明 (int) 范围内的数不会出错。
代码中我用的 (int) 类型，不过实际上 (Miller : Rabin) 素数测试可以承受更大的范围。
另外，如果是求一个 (long long) 类型的平方，可能会爆掉，因此有时我们要用快速幂，不能直接乘

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;

int prime[10]={2,3,5,7,11,13,17,19,23,29};
inline int Quick_Multiply(int a, int b, int c){  //快速乘
    int ans = 0;
    while(b){
        if(b & 1) ans = (ans + a) % c;
	    a = (a + a) % c;
	    b >>= 1;
    }
    return ans;
}

inline int Quick_Power(int a, int b, int c){    //快速幂
    int ans = 1;
    while(b){
        if(b & 1) ans = Quick_Multiply(ans, a, c);
        a = Quick_Multiply(a, a, c);
        b >>= 1;
    }
    return ans;
}

inline bool Miller_Rabin(int x){     //判断素数
    int i, j, k;
    int s = 0, t = x - 1;
    if(x == 2)  return true;   //2是素数 
    if(x < 2 || !(x & 1))  return false;     //如果x是偶数或者是0,1，那它不是素数 
    while(!(t & 1)){  //将x分解成(2^s)*t的样子
        s++;
        t >>= 1;
    }
    for(i = 0; i < 10 && prime[i] < x; ++i){      //随便选一个素数进行测试 
        int a = prime[i];
        int b = Quick_Power(a, t, x);      //先算出a^t
        for(j = 1; j <= s; ++j){    //然后进行s次平方 
            k = Quick_Multiply(b, b, x);   //求b的平方 
            if(k == 1 && b != 1 && b != x - 1)     //用二次探测判断 
            	return false;
            b = k;
        }
        if(b != 1)  return false;   //用费马小定律判断 
    }
    return true;   //如果进行多次测试都是对的，那么x就很有可能是素数 
}

signed main(){
    int x;
    scanf("%lld", &x);
    if(Miller_Rabin(x)) printf("Yes
");
    else printf("No
");
    return 0;
}

总结

终于写完了，一晚上就学习了这一个算法
(Markdown)敲起来真费劲，但是 $ LaTeX $ 是真的好看
感觉这篇博客写的很认真，希望能自我提升，也能帮到大家～～