有時候我們想快速的知道一個數是不是素數，而這個數又特别的大導緻 $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
個性簽名：時間會解決一切