有时候我们想快速的知道一个数是不是素数，而这个数又特别的大导致 $O(\sqrt n)$ 的算法也难以通过，这时候我们可以对其进行 Miller-Rabin 素数测试，可以很大概率测出其是否为素数。
（1）费马小定理：当 $p$ 为质数，有 $a^{p-1}\equiv 1(mod \ p)$，反过来不一定成立，也就是说，如果 $a, \ p$ 互质，且 $a^{p-1}\equiv 1(mod \ p)$，不能推出 $p$ 是质数，比如 $Carmichael$ 数
（2）二次探测：如果 $p$ 是素数，$0 < x < p$，则方程 $x^2 \equiv 1(mod \ p)$ 的解为 $x=1$ 或 $x=p-1$.
证一下二次探测定理：
易知 $ x^2-1 \equiv 0(mod \ p)$
$\because(x+1)(x-1) \equiv 0\ (mod \ p)$
$\because$ $p$ 为素数，只能分解为
$\because x+1 \equiv 0\ (mod \ p)$ 或 $x-1 \equiv 0\ (mod \ p)$
根据 $x$ 的取值范围，$x=1$ 或 $x=p-1$.
只根据费马小定理，易得一种检测质数的思路：
它的基本思想就是多次从 $\left [ 2, n-1 \right ]$ 中选取基 $a$，并检验是否每次都有 $a^{n-1} \equiv 1\ (mod \ n)$
遗憾的是，由于费马小定理的逆定理并不成立 ，即满足 $a^{n-1} \equiv 1\ (mod \ n)$，$n$ 也不一定是素数。
上面的做法中随机地选择 $a$，很大程度上降低了犯错概率，但是仍有一类数，上面的做法并不能准确地判断。
对于合数，如果对于所有与 $n$ 互素的正整数 $a$，都有同余式 $a^{n-1} \equiv 1\ (mod \ n)$ 成立，则合数 $n$ 为卡迈克尔数（Carmichael Number），又称费马伪素数。
而且我们知道，若 $n$ 为卡迈克尔数，则 $2^n-1$ 也是卡迈克尔数，从而卡迈克尔数的个数是无穷的。
在1~100000000范围内的整数中，只有255个Carmichael数。前3个Carmichael数是561,1105,1729。
根据卡迈克尔数的性质，可知其一定不是 $p^e$.
不妨将费马小定理和二次探测定理结合起来使用：
对偶数和0、1、2直接判断
设要测试的数为 $n$，设$m$、$k$，满足 $n-1 = m2^k$（使其中 $m$ 为奇数）
我们先算出 $a^t$，然后不断地平方且进行二次探测（进行 $k$ 次）
最后根据费马小定理探测一次
多次取不同的 $a$ 进行上面3步
可以证明Miller-Rabbin算法单次出错的概率小于等于 $\frac{1}{4}$，若重复 $k$ 次，则出错概率降低至 ${(\frac{1}{4})}^k$。这是一个很保守的估计，实际效果要好得多。
View Code
注：
（1）时间复杂度 $O(Slog^3)$（$S$ 为测试次数）
（2）long long相乘可能会爆long long，所以使用快速乘
（3）当 $a$ 取遍30内的素数，$int$ 都不会出错
（4）记住几个素数19260817、23456789、2092876369、11111111111111111111111（23个1）
（5）还可以去 hihocodeCoder 1287 测一下板子
参考链接：
1. 百度百科——卡迈克尔数
2. OI WIKI——素数
5. http://www.matrix67.com/blog/archives/234
个性签名：时间会解决一切