Miller-Rabin测试适合大整数因其时间复杂度O(k log³n)远优于试除法的O(√n)，且通过确定性基底或20轮随机基底可使误判率低于10⁻¹²；C++实现需定制mul_mod和pow_mod防溢出。
Miller-Rabin 测试为什么适合大整数
普通试除法对几百位的整数完全不可行——时间复杂度是 O(√n)，而一个 200 位十进制数的平方根约有 100 位，根本没法遍历。Miller-Rabin 是概率性素数测试，单次运行时间只和位数成线性关系（O(k log³n)），且错误率可压到 4⁻ᵏ。对 64 位以内整数，用确定性基底（如 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}）就能 100% 正确；对更大整数，选足够多的随机基底（比如 20 轮）实际误判概率低于 10⁻¹²，比硬件出错率还低。
如何用 C++ 实现模幂和大整数乘法
标准库没有原生大整数支持，必须自己处理溢出。关键不是“写个 BigInteger 类”，而是针对 Miller-Rabin 的特定需求做最小实现：只需要 mul_mod(a, b, mod) 和 pow_mod(base, exp, mod)。64 位系统下，两个 uint64_t 相乘可能溢出，不能直接用 a * b % mod。
推荐用“二进制拆分 + 模加”实现 mul_mod：
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t mod) {
uint64_t res = 0;
a %= mod; b %= mod;
while (b) {
if (b & 1) res = (res + a) % mod;
a = (a << 1) % mod;
b >>= 1;
}
return res;
}注意：a 可能溢出，所以每次都要 <code>% mod；若 mod 接近 UINT64_MAX，更稳妥的做法是用 __int128（GCC 支持）或调用汇编 mulx 指令，但绝大多数竞赛/工程场景用上面的版本足够。
立即学习“C++免费学习笔记（深入）”；
确定性基底选择与 64 位整数的特例
对 uint64_t 范围内的数（n ），已证明只需测试固定基底集合即可完全确定素性。不用随机，不需配置轮数，结果 100% 可靠。
- 若
n ，用基底 <code>{2, 7, 61}即可覆盖全部情况 - 若
2³² ≤ n ，必须用 <code>{2, 325, 9375, 28178, 450775, 9780504, 1795265022}（共 7 个） - 别硬背——直接抄权威来源（如 miller-rabin.appspot.com），否则漏一个就可能把
3215031751（强伪证数）判为素数
示例片段：
bool is_prime(uint64_t n) {
if (n < 2) return false;
if (n == 2) return true;
if ((n & 1) == 0) return false;
// 分解 n-1 = d * 2^r
uint64_t d = n - 1;
int r = 0;
while ((d & 1) == 0) { d >>= 1; r++; }
// 对每个确定性基底测试
for (uint64_t a : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
if (a >= n) continue;
uint64_t x = pow_mod(a, d, n);
if (x == 1 || x == n-1) continue;
bool ok = false;
for (int i = 1; i < r; i++) {
x = mul_mod(x, x, n);
if (x == n-1) { ok = true; break; }
}
if (!ok) return false;
}
return true;
}超过 64 位时怎么处理
一旦 n 超过 uint64_t 表示范围（比如读入字符串或用 std::vector<uint64_t></uint64_t> 存储），mul_mod 和 pow_mod 就必须基于任意精度整数实现。此时别从零造轮子——用 boost::multiprecision::cpp_int 或 GMP 库。
重点不是算法逻辑变化，而是接口适配：
-
cpp_int重载了%和*，但默认乘法不防溢出，得显式调用mul_mod(a, b, mod)（boost 提供） - 用 GMP 时，对应函数是
mpz_powm()和mpz_mulm()，参数全是mpz_t*，必须先mpz_init() - 性能瓶颈在模乘，GMP 的底层优化远好于手写，尤其对几千位整数
真正容易被忽略的是：Miller-Rabin 的“轮数”和“安全强度”不是线性关系。20 轮能把误报率压到 4⁻²⁰ ≈ 10⁻¹²，但 30 轮是 10⁻¹⁸——提升六个数量级，耗时却只多 50%。如果目标是密码学用途（比如生成 RSA 密钥），宁可多跑几轮，别省这点 CPU 时间。
