Miller-Rabin素数测试算法学习

定义
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)
[because a neq b (mod p), (c, p) = 1 ]
[therefore ac neq bc(mod p) ]
[therefore 1*2*3...(p - 1) equiv a*2a*3a...(p-1)a (mod p) ]
[therefore (p-1)! equiv (p-1)!a^{p-1}(mod p) ]
[because ((p-1)!, p) equiv 1 ]
[therefore a^{p-1} equiv 1(mod p) ]
二次探测定理
性质
如果(p)是一个素数，且(0证明
[because x^2 - 1 equiv 0(mod p) ]
[therefore (x + 1)(x - 1) equiv 0(mod p) ]
[therefore p|(x -1)(x + 1) ]
[because x < p ]
[therefore x = 1, x =p -1 ]
Wilson定理
性质
在初等数论中，威尔逊定理给出了判定一个自然数是否为素数的充分必要条件。
即：当且仅当p为素数时：(( p -1 )! ≡ -1 ( mod p ))
由于阶乘是呈爆炸增长的，其结论对于实际操作意义不大，但借助计算机的运算能力有广泛的应用，也可以辅助数学推导。

证明
由二次探测定理，(1*(p - 1))