# 米勒罗宾（Miller Rabin）素数检验 By [TrantorFarmer](https://paragraph.com/@trantorfarmer) · 2022-02-22 --- 给定一个正整数，如何快速的判定它是否是个素数是个经典问题。传统的方法就是[试除法](https://zh.wikipedia.org/wiki/%E8%AF%95%E9%99%A4%E6%B3%95)和[筛法](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)，这些方法对于较小的素数（如一百万以内）判定比较实用，但是对于更大的正整数却显得力不从心。好在人类的智慧是无穷尽的，总会找到更快的办法，米勒罗宾素数检验一个更快的方法。 ### 米勒罗宾素数检验 顾名思义，米勒和罗宾是两个人，米勒罗宾素数检验算法其实是两个算法，米勒检验是素数检验，罗宾定理是概率性检验。但是在用作素数检验的时候这两个算法一般被合在一起，因此不做区分。这个算法的主要难点在米勒检验，在介绍米勒检验之前，需要一点预备知识，先介绍一下费马小定理。 #### 费马小定理 如果p是素数，对于任意正整数a，则有$$a^p \\equiv a \\pmod p$$。 特别的，如果p是素数，而且a和p互素，则可以从等式两边同时除以a，有\\(a^{p-1} \\equiv 1 \\pmod p\\)。 但是，费马小定理的逆命题并不成立，也就是说，对于互素的正整数a和p，如果有\\(a^{p-1} \\equiv 1 \\pmod p\\)，则p不一定是素数。 例如，341就是让费马小定理逆命题不成立的最好例子，对于a=2，p=341，有\\(2^{340} \\equiv 1 \\pmod {341}\\)。因为\\(2^{10} \\equiv 1 \\pmod {341}\\)，而\\(2^{340} \\equiv {(2^{10})}^{34}\\)，但是341是一个合数（\\(341 = 11 \\times 31\\)）。对于这类满足这类条件的正整数，称之为\*\*[伪素数](https://zh.wikipedia.org/wiki/%E4%BC%AA%E7%B4%A0%E6%95%B0)\*\*，伪素数非常稀少，但是却有无穷多个。 因此费马小定理不能作为判断素数的充要条件，顺便提一下，\*\*[威尔逊定理](https://zh.wikipedia.org/wiki/%E5%A8%81%E5%B0%94%E9%80%8A%E5%AE%9A%E7%90%86)\*\*可以作为判断素数的重要条件。有了费马小定理的基础，再来看看米勒检验就好理解一点。如前所述，费马小定理的逆并不成立，但是它的逆否命题是成立的。也就是说，对于任意正整数a，如果 \\(a^{p-1} \\neq 1 \\pmod p\\)，则p肯定不是素数。因此对于任意的正整数，费马小定理给出了非素数判断的强有力的验证，米勒建议正式利用了这一性质。 #### 米勒检验 对于任意正整数a，和奇整数n，有\\(n-1 = 2^{s}d(s \\ge 0)\\)，d是奇数。如果\\(a^{d} \\equiv 1 \\pmod n\\)，或者存在\\(i(0 \\le i \\le {s-1})\\)使得\\(a^{2^{i}d} \\equiv -1 \\pmod n\\)，则\\(a^{2^{s}d} \\equiv a^{n-1} \\equiv 1 \\pmod n\\)，称n通过了基为a的米勒检验，n很有可能是个素数。 **几个需要注意的点** _为什么是奇整数n？_ > * 因为偶的素数只有2. > _为什么\\(a^{2^{i}d} \\pmod p(0 \\le i \\le s-1)\\)要等于-1，而不是1？_ > * 如果n通过了米勒检验，序列\\(a^{d},a^{2d},a^{2^{2}d},...,a^{2^{s}d}\\)将以1结束，并且在序列的第一个1前面的将是n-1。因为\\(x^{2} \\equiv 1 \\pmod p\\)，则有x=1或者x=-1。同理，如果该序列出现了n-1，则下一个值一定是1，因为\\((n-1)^{2} \\equiv n^2-2n+1 \\equiv 1\\pmod p\\)。 > 理解了米勒检测，基本上就理解了整个算法了，因为罗宾定理给出了一个概率性的结论，它的证明比较复杂，这里就略过了，直接给出结论。 #### 罗宾定理 设n是一个正整数，选取k个不同的小于n的正整数作为基，并且对每一个基做米勒检验。若n是一个合数，则n通过所有k个米勒检验的概率不会超过\\({(\\frac{1}{4})}^{k}\\) 若我们在1~n之间随机选取100个不同的整数作为基，并且以这100个整数为基做一次米勒检验，那n通过所有检验的概率要小于\\({(10)}^{-60}\\)，这个概率甚至比计算机硬件出错的概率都要小，因此，我们没有理由认为n不是一个素数。 ### 总结 有了米勒的素数检验以及罗宾定理的概率性检验作为基础，我们可以快速的对一个大整数进行素数判断。好的算法需要数学原理的支撑，只有理解了这些原理才能写出高效简洁的代码。 --- *Originally published on [TrantorFarmer](https://paragraph.com/@trantorfarmer/miller-rabin)*