强伪素数测试本质是以高概率排除合数而非确定素性；需用boost::multiprecision等库处理大整数，手动实现防溢出的模乘与快速幂，随机选取底数并执行s轮平方检验。
强伪素数测试本质是啥
强伪素数测试（Miller–Rabin）不是直接“判断是否为素数”，而是以高概率排除合数。对大整数来说，它只告诉你“大概率是素数”或“确定是合数”。C++标准库不提供任意精度整数，所以必须用第三方库（如 boost::multiprecision::cpp_int 或 GMP）处理大整数，否则 long long 顶多撑到 10¹⁸，远不够“大整数”场景。
常见错误是：拿 int 或 unsigned long long 做模幂运算，中间结果溢出导致误判——比如 pow_mod( a, r, n ) 若没用模乘防溢出，结果全错。
用 boost::multiprecision 实现模幂和测试
boost::multiprecision::cpp_int 支持任意精度，但自带的 powm（即模幂）函数在较新版本中才稳定。推荐手动实现带溢出防护的模乘 + 快速幂：
关键点：
- 必须用
multiply_mod或手写mul_mod(a, b, mod)，不能先乘再取模——a * b可能远超cpp_int临时容量或触发隐式转换失败 - 测试轮数选 10–20 次足够：对 2048 位数，
20轮误判率低于4^(-20)≈ 10⁻¹² - 底数
a必须在[2, n-2]范围内随机选取；固定底数（如只用 2, 3, 5）仅对n 有确定性保证，不适用于真正的大整数
cpp_int mul_mod(cpp_int a, cpp_int b, const cpp_int& mod) {
cpp_int res = 0;
a %= mod; b %= mod;
while (b > 0) {
if (b & 1) res = (res + a) % mod;
a = (a >= 1;
}
return res;
}
<p>cpp_int pow_mod(cpp_int base, cpp_int exp, const cpp_int& mod) {
cpp_int res = 1;
while (exp > 0) {
if (exp & 1) res = mul_mod(res, base, mod);
base = mul_mod(base, base, mod);
exp >>= 1;
}
return res;
}</p>
执行 Miller–Rabin 的核心逻辑
输入大整数 n，先特判小值（n → 合数；<code>n == 2 → 素数；偶数 → 合数），再分解 n - 1 = d * 2^s：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
然后对每个随机底数 a 执行：
- 计算
x = pow_mod(a, d, n) - 若
x == 1 || x == n-1，本轮通过，跳下一轮 - 否则循环
s-1次：x = pow_mod(x, 2, n)，任一结果等于n-1则通过 - 若全不满足，
n是合数，立即返回false
注意：所有中间变量（d、s、x）都必须是 cpp_int 类型；用 int 存 s 没问题（因 n 是 b 位数时 s ），但别用 <code>int 存 d——它可能接近 n 本身。
容易被忽略的边界与性能坑
最常被跳过的点：
-
n == 1必须显式判为合数——很多实现漏掉，导致pow_mod在模 1 下行为未定义或卡死 - 随机数生成器必须支持
cpp_int范围：用std::uniform_int_distribution配std::mt19937_64只能生成 64 位随机数，需用boost::random::uniform_int_distribution<cpp_int></cpp_int>或分段构造 - 多次调用
pow_mod时，若n固定，可预计算蒙哥马利参数加速，但boost::multiprecision默认不启用——实际项目中若频繁测同一组数，值得自己封装带缓存的模幂类
真正的大整数（比如 RSA 密钥生成中的 2048 位数）做一次 Miller–Rabin 通常要几毫秒，但 20 轮就是几十毫秒。如果追求极致速度，GMP 的 mpz_probab_prime_p 内部做了大量优化，比手写 boost 版快 3–5 倍，且默认使用经过验证的底数集。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
