米勒-拉賓質數測試（Miller-Rabin primality test）
/ MILL-er RAH-bin /
一個 600 位數是質數嗎？想用每個較小的數、甚至只用到它平方根為止的每個數去除它，在那種大小下完全沒指望。米勒-拉賓（Miller-Rabin）是判斷大數是否為質數的快速隨機方法。它不分解任何東西；而是用幾個隨機「見證者」盤問這個數，每個見證者要嘛揭穿這個數一定是合數，要嘛沒揭穿——而足夠多的「沒揭穿」就讓我們有信心它是質數。它正是真實密碼學函式庫用來產生 RSA 所需大質數的測試。
這個測試建立在費馬小定理之上：若 n 為質數，則對任意底數 a，a^(n-1) = 1 mod n。強化（米勒-拉賓）版把它磨利。把 n - 1 = d * 2^s 寫成 d 為奇數。若 n 為質數，則對隨機底數 a，要嘛 a^d = 1 mod n，要嘛 a^d, a^(2d), a^(4d), ..., a^(2^(s-1) d) 之一等於 -1 mod n（這些是 1 的平方根，而模質數時 1 的平方根只有 +1 與 -1）。若兩條件皆不成立，則 a 就是證明 n 為合數的見證者——真正的質數絕不會失敗。演算法挑一個隨機 a，算 a^d mod n 並反覆平方（用快速模冪），檢查這個型態。若某見證者沒揭穿 n，就再試另一個隨機 a。追蹤的味道：對真質數，每個底數都遵守該型態；對像 561 這樣的合數（一個能騙過單純費馬測試的卡邁克爾數），多數隨機底數都能抓到它，因為強平方根條件較難偽裝。
誠實的核心是：米勒-拉賓是蒙地卡羅、單邊錯誤的測試。若它曾回報「合數」，那是確定的——見證者就是證明。若它回報「可能是質數」，則有微小的出錯機會：對一個合數，一個隨機底數沒能成為見證者的機率至多 1/4，所以跑 k 個獨立隨機底數把錯誤壓到 (1/4)^k 以下，例如 40 輪就讓「假質數」的機率小到天文等級。所以你能以多跑幾輪為代價，把錯誤弄得要多小有多小，但它永不恰好為零（除非你用一組已被證明在某已知界內有效的決定性底數）。每輪花 O(log n) 次模乘法，所以即使在密碼學規模下整個測試也很快——這正是它成為標準質數產生器的原因。
測試 n=561（= 3*11*17，合數）。n-1 = 560 = 35 * 2^4，故 d=35、s=4。取底數 a=2：算 2^35 mod 561，再反覆平方。這串值未循所需型態經由 -1 步驟到達 1，所以 a=2 是見證者，米勒-拉賓正確回報「合數」——儘管 561 對某些底數能通過較弱的單純費馬測試。
一個見證者確切證明是合數；通過 k 個隨機底數則錯誤低於 (1/4)^k。
錯誤是單邊的：「合數」是確定的，「質數」只是可能——k 輪的假質數風險至多 (1/4)^k，很小但永不恰好為零，除非使用已證明有效的決定性底數組。