因为long long最大仅支持约19位十进制数，而miller-rabin常用于判断上百至上千位大整数（如rsa密钥候选数），必须依赖boost::multiprecision::cpp_int等高精度库或手写防溢出模幂运算，否则中间乘法a*b极易溢出导致未定义行为。
Miller-Rabin 测试在 C++ 中为什么不能直接用 int 或 long long
因为 Miller-Rabin 通常用于判断上百位甚至上千位的整数是否为质数，而 long long 最大只能表示约 19 位十进制数。一旦输入是字符串形式的大数（比如 "123456789012345678901234567890"），就必须先转成支持高精度运算的结构——但标准 C++ 没有内置大整数类型。
实际做法是：用第三方库（如 boost::multiprecision::cpp_int）或手写模幂/乘法，避免中间结果溢出。最常见踩坑是：用 long long 做 a * b % mod，其中 a 和 b 接近 mod，乘积远超 LLONG_MAX，导致未定义行为。
- 必须用快速乘法（binary multiplication + mod）替代直接乘法
- 模幂函数
mod_pow的底数、指数、模数都得是同一高精度类型 - 如果只测 64 位以内整数，可用
__int128（GCC 支持），但不可跨平台依赖
如何选合适的底数 a（witness）让测试既快又可靠
Miller-Rabin 是概率算法，但对确定范围内的数，存在已知的确定性 witness 集合。例如：
- 对
n ，只需测试 <code>a ∈ {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}—— 这是目前已知最小完备集 - 对
n ，仅需 <code>{2, 7, 61}就能 100% 判定（无误判） - 别用随机
a碰运气，尤其在线上判题或密码场景中，确定性比“平均快”重要得多
注意：底数必须满足 1 ，且 <code>gcd(a, n) == 1；若不满足，可直接返回合数（因为找到非平凡因子）。
mod_mul 和 mod_pow 怎么写才不爆 long long
核心是把乘法拆成二进制加法，每步都取模：
long long mod_mul(long long a, long long b, long long mod) {
long long res = 0;
while (b > 0) {
if (b & 1) res = (res + a) % mod;
a = (a >= 1;
}
return res;
}
<p>long long mod_pow(long long base, long long exp, long long mod) {
long long res = 1;
while (exp > 0) {
if (exp & 1) res = mod_mul(res, base, mod);
base = mod_mul(base, base, mod);
exp >>= 1;
}
return res;
}</p>
这个 mod_mul 时间复杂度是 O(log b)，比浮点技巧（如 __int128 强转）更可移植；但如果 mod 接近 2^63，a 仍可能溢出 —— 此时应改用 <code>__int128 版本或调用 boost::multiprecision。
完整 Miller-Rabin 判定逻辑里最容易漏掉的步骤
标准流程是把 n−1 写成 d × 2^r（d 为奇数），然后检查是否存在 a^d ≡ 1 (mod n) 或某个 a^(d×2^i) ≡ −1 (mod n)。但容易忽略：
-
n必须先特判小素数：n → 合数；<code>n == 2→ 素数；n为偶数且 ≠2 → 合数 - 对
n == 1，必须返回 false（1 不是质数） - 在循环中计算
a^d mod n后，若结果为 1 或n−1，可提前退出当前 witness 测试（不是继续下一轮） - 每次平方后都要检查是否等于
n−1，且仅当i 时才允许接受该条件（否则就退化成最后一步了）
真正难调试的点在于：当 n 是 Carmichael 数（如 561、1105）时，某些 a 会让所有中间结果“看起来像素数”，所以 witness 集合不能随意缩减 —— 尤其别为了省时间只试一个 a=2。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
