miller-rabin测试的核心逻辑是：将n−1分解为d×2^r（d为奇数），对基底a计算a^d mod n，再迭代平方r次，检查是否出现1或n−1；若对所有选定基底均满足条件，则判定为素数。
Miller-Rabin测试的核心逻辑是什么
Miller-Rabin不是直接判断“是不是素数”，而是判断“是不是强伪素数”——即对某个底数 a 满足强伪素性条件的合数。真正想用它做素性判定，必须配合多个底数测试，并依赖已知的确定性基底集（如对 64 位整数，用 {2, 325, 9375, 28178, 450775, 9780504, 1795265022} 可保证 100% 正确）。
关键步骤是把 n−1 写成 d × 2^r 形式（d 为奇数），然后计算 a^d mod n，再反复平方 r 次，检查是否出现 1 或 n−1。
如何安全实现大整数模幂（避免溢出）
C++ 标准库不提供原生大整数，long long 最多支持约 1e18，而 Miller-Rabin 中的乘法（如 a * a % n）极易溢出。必须手写或调用支持模乘的函数。
- 用
__int128（GCC/Clang 支持）可覆盖到约1e38：先做乘法再取模，但需确认编译器和平台支持 - 否则必须用快速乘（binary multiplication）：把
a * b % mod拆成类似快速幂的加法循环，每次加法后取模 - 不要用
double中转或浮点近似——精度丢失会导致误判 - 示例快速乘（
mul_mod）：long long mul_mod(long long a, long long b, long long mod) { long long res = 0; while (b) { if (b & 1) res = (res + a) % mod; a = (a + a) % mod; b >>= 1; } return res; }
哪些底数能保证 64 位整数的确定性判定
对 n ，已证明只需测试固定 7 个底数即可完全避免漏判合数。这不是经验性选择，而是数学验证过的最小完备集。
- 必须用
{2, 325, 9375, 28178, 450775, 9780504, 1795265022}，顺序无关，缺一不可 - 只用
2和3会漏掉像2047这样的强伪素数（2047 = 23 × 89） - 如果输入可能小于
2^32，可用更小集合（如{2, 7, 61}），但跨平台统一用 7 元组更省心 - 注意：所有底数都应先对
n取模，且若a % n == 0，直接跳过该轮（此时n显然不是素数）
容易被忽略的边界与预处理
Miller-Rabin 是概率算法的确定性变体，但前提是输入合法、预处理到位。漏掉这些，再正确的模幂也会返回错误结果。
- 先特判小素数：
n → false；<code>n == 2→ true；n为偶数且 ≠2 → false -
n必须是奇数且 ≥3 才进入主循环，否则r计算会出错（n−1无法表示为d×2^r） - 分解
n−1时，用while ((n-1) % 2 == 0)循环求r，别用位运算假设n−1一定有足够低位零 - 模幂过程中，若中间结果为
0或1，要提前终止该轮——这是合数的明确信号，不是继续算完再说
真正麻烦的从来不是算法本身，而是怎么让 mul_mod 在不同编译器下都不溢出，以及怎么确保那 7 个底数一个没少、一个没写错。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
