miller-rabin测试需大整数运算支持，标准c++类型无法处理200位数，必须用大整数库或手写防溢出的模幂运算；推荐arnabk96/bigint或boost::multiprecision::cpp_int，手写需实现mul_mod并用快速幂，底数选择对64位数可确定性验证，超大整数则只能概率性测试。
Miller-Rabin 测试需要大整数运算支持
标准 C++ 的 int、long long 无法表示“超大整数”（比如 200 位十进制数），直接调用 pow 或取模会溢出或得到错误结果。必须先用大整数库，或手写模幂运算——但手写需严格避免中间结果溢出。
常见错误是：用 __int128 尝试撑到 40 位左右，但一旦输入超过约 35 位十进制数（即 > 2ⁱ¹⁰），__int128 乘法仍会溢出；更危险的是，有人直接用 std::pow 算 a^d mod n，这在数值远超 double 精度时完全不可靠。
- 推荐用已验证的轻量库，如 arnabk96/BigInt（头文件仅、支持
%和*重载）或boost::multiprecision::cpp_int - 若坚持手写，必须实现
mul_mod(a, b, m)：用类似俄罗斯农民乘法 + 模减法，每次加法后立即% m，确保中间值始终 -
boost::multiprecision::cpp_int默认启用模运算优化，但需显式开启#define BOOST_MULTIPRECISION_CPP_INT_BACKEND_NO_ET避免表达式模板引发的隐式转换 bug
如何正确分解 n−1 = d × 2^r
Miller-Rabin 的第一步是把待测数 n 减 1 后拆成奇数部分 d 和 2 的幂次 r。这个步骤看似简单，但对大整数容易出错：不能用位运算 n-1 >> 1 循环右移（cpp_int 不支持原生 >> 对大数的高效移位），也不能用除以 2 直到余数为 1——除法开销大且易写错终止条件。
- 用
while ((n_minus_1 & 1) == 0)判断最低位是否为 0（cpp_int支持&） - 每次循环做
n_minus_1 >>= 1（cpp_int重载了>>=，安全）并r++ - 最终
d就是循环结束后的n_minus_1值，不是原始n-1除以 2^r 的结果（避免额外除法）
模幂计算必须用快速幂+模乘防溢出
核心步骤 pow_mod(a, d, n) 如果直接递归或朴素循环，时间复杂度 O(d)，而 d 可能接近 n，完全不可行。必须用快速幂（binary exponentiation），且每一步乘法都要走 mul_mod。
- 不要写
result = (result * base) % n——result * base在cpp_int中虽不会溢出，但乘法本身可能慢一个数量级；用mul_mod(result, base, n)显式控制中间规模 - 底数
a必须先% n，否则a >= n会导致后续幂次计算错误（例如 a=100, n=13，不取模就从 100 开始平方，徒增计算量） - 测试集建议包含已知强伪素数，如
n = 2047（以 2 为底的强伪素数）、n = 1373653（以 2 和 3 为底的强伪素数），验证你的实现能否正确判为合数
选择哪些底数才能保证 64 位内确定性
对 uint64_t 范围内的数（≤ 2⁶⁴−1），已证明只需测试固定底数集合即可 100% 正确，无需随机采样。但注意：这个结论**不适用于任意长度的大整数**；对超大整数，只能用概率性测试，或依赖特定代数结构（如已知是 RSA 模数）。
- 若
n ，用底数 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 可确定性判断（J. Selfridge 提出，已被验证） - 若
n >= 2^64，标准做法是选前 12 个素数作底数（2,3,5,7,11,13,17,19,23,29,31,37），错误率低于 4⁻¹² ≈ 1/16M - 切勿用 rand() 生成底数——
rand()最大只到 RAND_MAX（常为 32767），远小于大整数，导致大量底数重复，实际错误率远高于理论值
真正难的不是算法逻辑，而是让每一步模运算既正确又不慢：大整数除法和取模仍是瓶颈，boost::multiprecision 在 n > 1000 位时会自动切换到 Karatsuba，但 mul_mod 若没利用该特性，性能会断崖下跌。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
