绝大多数场景下需手写Miller-Rabin——标准C++库不提供，boost支持弱，GMP依赖重；小于2^64用确定性底数集可100%正确，大于则需大数库且仍为概率算法。
Miller-Rabin 需要自己实现还是用现成库？
绝大多数场景下，Miller-Rabin 得自己写——标准 C++ 库不提供大整数质性测试，boost::multiprecision 虽有 is_prime()，但底层默认用的是确定性小范围筛 + 概率 Miller-Rabin，且对自定义大数支持弱；而 GMP（C 库）虽高效，但引入它会让项目依赖变重、跨平台编译麻烦。所以真要控制精度、速度和输入范围，手写一个轻量可靠的版本更实际。
关键点在于：你不需要从零实现大整数运算，而是假设已有能做模幂（mod_pow）、模乘（mod_mul）、减法和偶数判断的 uint64_t 或 __int128 封装类型。超过 2^64 的数必须用第三方大数（如 boost::multiprecision::cpp_int），但此时 Miller-Rabin 本身不是瓶颈，慢的是模乘。
- 小于
2^64：用 64 位整数 + 确定性底数集（见下条），100% 正确 - 大于
2^64：必须用大数库，但Miller-Rabin仍只是概率算法，需多轮；别指望单次调用就“保证质数” - 别把
rand()用在底数生成上——它周期短、低位劣质；改用std::random_device+std::mt19937_64
为什么 64 位内用 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 这组底数？
这不是经验值，是数学证明过的最小确定性集合：对所有 n ，用这 7 个底数做 <code>Miller-Rabin 测试，结果为“通过”当且仅当 n 是质数。比用随机底数快，且零误判。
常见错误是只用 {2, 3, 5, 7}——这对 int32_t 够用，但一到 uint64_t 范围，立刻漏掉像 3215031751 这样的强伪证（它被前 4 个底数都骗过）。还有的代码硬写 for (int a = 2; a ，既慢又不可靠。
立即学习“C++免费学习笔记（深入）”；
- 底数必须
，且与 <code>n互质；若n是偶数或小质数（2/3/5…），提前返回 - 对
n ，其实只用 <code>a = 2就够；但统一走 7 个底数分支反而更省逻辑判断 - 底数顺序无关正确性，但把小的放前面能更快排除合数（小底数模幂快，且很多合数第一轮就失败）
模幂和模乘怎么写才不溢出、不丢精度？
核心陷阱是：(a * b) % n 在 a 和 b 接近 UINT64_MAX 时必然溢出。不能直接乘，得拆解。64 位下推荐用 __int128（GCC/Clang 支持），它天然支持 128 位中间结果：
uint64_t mod_mul(uint64_t a, uint64_t b, uint64_t m) {
return (uint64_t)((__int128)a * b % m);
}没 __int128？就得用二进制拆分的倍增法（类似快速幂思想），时间多常数 2–3 倍，但安全：
uint64_t mod_mul(uint64_t a, uint64_t b, uint64_t m) {
uint64_t res = 0;
while (b > 0) {
if (b & 1) res = (res + a) % m;
a = (a << 1) % m;
b >>= 1;
}
return res;
}-
mod_pow必须基于安全的mod_mul，不能用原生* - 所有中间变量（包括
n-1的分解结果）都声明为uint64_t，避免隐式符号转换引发负数模行为 - 测试前先检查
n 、<code>n == 2、n % 2 == 0，这些情况根本不用进主循环
误报率和轮数之间到底什么关系？
每轮独立随机底数的误报率 ≤ 1/4，k 轮后 ≤ 4⁻ᵏ。但这是理论上界，实际远更低。问题在于：你根本不需要靠堆轮数来“补救”不可靠的实现。重点应放在——
- 小范围（
n ）直接试除，比跑 20 轮 <code>Miller-Rabin还快 - 64 位内老实用那 7 个确定性底数，别谈“概率”，就是确定性算法
- 真要处理任意长度大数（比如 1024-bit RSA 模数），轮数设 64 是工程惯例；再往上收益极小，瓶颈早变成大数模乘了
- 别信“用
time(NULL)当随机种子”——密码学强度不重要，但至少别让每次运行都测同一组底数
最易被忽略的一点：Miller-Rabin 只说“很可能是质数”，但从不证明它是质数；如果你后续要用这个数做 RSA 密钥，必须接受它仍有极小概率是合数——而这个风险，往往比实现 bug 更难 debug。
