给定一个正整数，如何快速的判定它是否是个素数是个经典问题。传统的方法就是试除法和筛法，这些方法对于较小的素数（如一百万以内）判定比较实用，但是对于更大的正整数却显得力不从心。好在人类的智慧是无穷尽的，总会找到更快的办法，米勒罗宾素数检验一个更快的方法。
顾名思义，米勒和罗宾是两个人，米勒罗宾素数检验算法其实是两个算法，米勒检验是素数检验，罗宾定理是概率性检验。但是在用作素数检验的时候这两个算法一般被合在一起，因此不做区分。这个算法的主要难点在米勒检验，在介绍米勒检验之前，需要一点预备知识，先介绍一下费马小定理。
如果p是素数，对于任意正整数a，则有。 特别的，如果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\)）。对于这类满足这类条件的正整数，称之为**伪素数**，伪素数非常稀少，但是却有无穷多个。
因此费马小定理不能作为判断素数的充要条件，顺便提一下，**威尔逊定理**可以作为判断素数的重要条件。有了费马小定理的基础，再来看看米勒检验就好理解一点。如前所述，费马小定理的逆并不成立，但是它的逆否命题是成立的。也就是说，对于任意正整数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不是一个素数。
有了米勒的素数检验以及罗宾定理的概率性检验作为基础，我们可以快速的对一个大整数进行素数判断。好的算法需要数学原理的支撑，只有理解了这些原理才能写出高效简洁的代码。