米勒-拉宾测试在c++中不能直接用long long，因为其最大值约10¹⁸，而密码学场景常需处理2048位以上超大整数，远超内置类型范围；必须先用字符串、vector或boost::multiprecision等结构表示大数，再手写防溢出的模幂运算（如__int128乘模或倍增法），并严格预处理边界（n
米勒-拉宾测试在C++里为什么不能直接用 long long
因为 long long 最大只能表示约 10¹⁸ 量级的数，而米勒-拉宾常用于密码学场景下的超大整数（比如 2048 位或更大），远超内置整型范围。你得先有能存下它的数据结构——通常用 vector<uint64_t></uint64_t> 或第三方库如 boost::multiprecision::cpp_int，否则连输入都读不进来。
别急着写测试逻辑，先确认你手里的“超大整数”是怎么表示的：是字符串？十六进制字节数组？还是已经封装好的大数类？不同表示方式影响后续模幂运算的实现路径。
如何实现模幂运算（mod_pow）才能不溢出
标准 pow(a, b) % m 在大数下完全不可用，必须手写快速幂 + 模乘防溢出。核心难点是 a * b % m 这一步：即使 a 和 b 都小于 m，乘积仍可能远超 uint64_t 上限。
- 若使用
__int128（GCC/Clang 支持），可直接做(__int128)a * b % m，但注意 Windows MSVC 不支持 - 若只能用
uint64_t，需用“倍增法”模拟乘法：把b拆成二进制位，每次累加a * 2^k % m，类似快速幂但内层是加法循环 - 若用
boost::multiprecision，直接调powm(a, b, m)，底层已处理溢出，但性能比手写慢 3–5 倍
示例（基于 __int128 的模乘）：
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {
return (uint64_t)((__int128)a * b % m);
}
米勒-拉宾主流程中容易漏掉的边界检查
很多实现只关注“随机选底数”，却忽略几个关键预处理步骤，导致对小合数（如 4、6、8、9）或小素数（如 2、3、5）误判。
- 先特判
n → 返回 false；<code>n == 2→ true；n % 2 == 0→ false（除非 n==2） - 对
n 的数，建议直接用试除法（最多试到 sqrt(n) ≈ 10），比跑米勒-拉宾还快且确定 - 分解
n - 1为d * 2^r时，确保d是奇数：反复右移直到(n-1) & 1为真，计数移位次数 - 选底数
a时，必须满足1 ，且 <code>gcd(a, n) == 1；若gcd != 1，说明n显然合数，可直接返回 false
确定性测试：选哪几个底数才能保证 64 位内结果正确
对 uint64_t 范围内的数（即 n ），不需要随机采样。已有数学证明：用固定底数集就能 100% 判定。
推荐使用以下 7 个底数（来自 Jim Sinclair 2013 年验证）：
{2, 325, 9375, 28178, 450775, 9780504, 1795265022}
只要对每个 a 都通过测试，就可断定 n 是素数；任一失败即合数。这比用 rand() 反复试更可靠，也更快。
注意：这个集合仅适用于 n 。如果你的“超大整数”超过这个范围（比如 1000 位），就必须用概率版本，并配合大数库实现模幂——此时错误率可压到 <code>4^(-k)（k 为轮数），通常 k=64 就足够安全。
真正麻烦的从来不是算法逻辑，而是把大数的加、减、乘、模、比较全都无错实现一遍。哪怕只漏一个 carry 处理，整个素性判断就全崩了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
