64位整数确定性Miller-Rabin需用固定基数集：n<2³²时用{2,7,61}，n<2⁶⁴时用{2,325,9375,28178,450775,9780504,1795265022}；必须预判n≤61的质数并特判，不可依赖随机底数。
64位整数用哪几个基数能100%确定判定
对 uint64_t 范围内的正整数（即 ≤ 18446744073709551615），Miller-Rabin 不需要随机选底数，也不需要跑20轮——固定一组小整数就能做到**确定性判定**，零误判。
关键分两档：
- 若
n < 2^32（即 ≤ 4294967295），只需测试{2, 7, 61}—— 3个数，快且全覆盖 - 若
n < 2^64（完整 uint64_t 范围），必须用{2, 325, 9375, 28178, 450775, 9780504, 1795265022}—— 7个数，这是 Grantham 2001 年证明的最小完备集
别用 {2, 3, 5, 7} 或自己拍脑袋选——它们在 64 位范围内有明确反例（比如 n = 3215031751 就能骗过前4个）。
为什么不能直接用 rand() 生成随机底数
随机底数看似“更安全”，实则对 64 位数是倒退：不仅慢，还引入不确定性风险。
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 若
a % n == 0（比如n = 1000000007，而rand()恰好返回它的倍数），powmod(a, d, n)会算出 0，直接误判为合数 - 更隐蔽的是：某些强伪素数（如
n = 2047）对小底数敏感，但对大底数反而“免疫”；随机选可能漏掉关键 witness - OJ 或加密场景要求可复现结果，随机化破坏 determinism，调试和验证都变困难
结论：固定集 + 确定性执行 是工程落地的唯一合理选择。
基数必须小于 n，且要提前特判小值
算法逻辑要求每个底数 a 满足 1 < a < n。但实际写代码时不能只靠循环里 if (a >= n) continue 来跳过——这掩盖了边界漏洞。
-
n == 2必须直接返回true：所有底数集都含2，若不提前拦住，a == n会导致模幂计算异常（如powmod(2, 1, 2)返回 0） -
n == 3, 5, 7, ...同理：若底数等于n，取模后为 0，后续判断全错 - 正确做法：在进入主循环前，先做
if (n <= 61) return n == 2 || n == 3 || n == 5 || n == 7 || ...—— 把所有基数里的值都列出来硬判
否则，哪怕只漏一个 n == 61，整个确定性保证就崩了。
超64位大整数怎么设基数
一旦 n 超过 uint64_t（比如 200 位十进制数），就不存在“确定性有限集”了——数学上已知：对任意有限底数集，总存在能骗过它的强伪素数。
- 此时只能退回到概率模型：选若干小质数（如
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}）或用std::random_device生成[2, n-2]内的随机数 - 推荐轮数
k = 20：误判率 ≤ 4⁻²⁰ ≈ 10⁻¹²，对绝大多数场景足够 - 注意：用大整数库（如
boost::multiprecision::cpp_int）时，务必确保a % n在传入powmod前已完成——否则a可能远大于n，徒增模幂开销
真正容易被忽略的点是：**确定性只存在于 64 位以内**；跨过这个边界，一切优化假设都要重来。
