米勒-拉宾素性测试
数学与数论 · 概率判素 · RSA 选质数的引擎
费马测试有个漏洞
RSA 要挑几百位的大质数，试除到 √n 是天文数字。费马小定理给了快测：n 是质数时对任意互质的 a 都有 a^(n−1) ≡ 1 (mod n)——反过来不成立也就罢了，还有一族卡迈克尔数专门捣乱：561 = 3·11·17 是合数，可 2^560 ≡ 1 (mod 561)，对所有互质底数都过费马测试。
在「开平方」处设卡
米勒-拉宾的加固点：质数模下 x² ≡ 1 只有两个解 x ≡ ±1。把 n−1 = 2^s·d（d 为奇数）拆开，从 x₀ = a^d 开始连续平方直到 a^(n−1)：若质数，这条链要么一路是 1、要么某处先撞到 −1 再变 1；若链从「既非 1 也非 −1」的数平方出 1——非平凡平方根现形，n 必是合数。
下面两行试验（底数 a=2）：41（真质数）链 32 → 40 = −1 撞 −1 通过；561（伪装者）链 263 → 166 → 67 → 1，67² ≡ 1 而 67 ≠ ±1——当场识破。点「下一步」逐格看平方链，判定步黄色高亮「作案证据」。右侧代码随每一步同步高亮。
| a^d | 平方¹ | 平方² | 平方³ | |
|---|---|---|---|---|
| 41（真质数） | ||||
| 561（伪装者） |
大数是不是质数？试除到 √n 太慢；费马测试 a^(n−1)≡1 会被卡迈克尔数骗过。米勒-拉宾在「开平方」处设卡：质数模下 x²≡1 只有 x≡±1 两个解
1function millerRabin(n: number, a: number): boolean {
2 let d = n - 1, s = 0;
3 while (d % 2 === 0) { d /= 2; s++; } // n−1 = 2^s·d
4 let x = powMod(a, d, n); // x = a^d
5 if (x === 1 || x === n - 1) return true;
6 for (let i = 1; i < s; i++) {
7 x = (x * x) % n; // 平方一步
8 if (x === n - 1) return true; // 撞到 −1 → 通过
9 if (x === 1) return false; // 非平凡平方根 → 合数
10 }
11 return false; // 从未撞到 −1 → 合数
12}
底数a = 2
1 / 12
概率界与工程实践
单轮：随机底数 a，合数通过测试的概率 ≤ 1/4（比费马强得多且无卡迈克尔死角）。
k 轮：误报 ≤ 4^(−k)——试 20 个底数就到 10^(−12) 量级。
确定性：对 64 位整数，试固定底数集 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 即可给出确定答案。
引擎：a^d 与平方全是模幂——快速幂是它的发动机。
k 轮：误报 ≤ 4^(−k)——试 20 个底数就到 10^(−12) 量级。
确定性：对 64 位整数，试固定底数集 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 即可给出确定答案。
引擎：a^d 与平方全是模幂——快速幂是它的发动机。
OpenSSL 生成 RSA 密钥、各语言大数库的 isProbablePrime，跑的都是米勒-拉宾（常配合 BPSW 组合测试）。数论线在此收官：筛法管小质数、米勒-拉宾管大质数、φ(n)与扩欧配钥匙、快速幂与CRT跑加解密——一条 RSA 流水线全通了。