Miller-Rabin素性判定的核心逻辑是：对奇数n>2，将其写为n−1=d×2^r（d为奇数），再选取基底a验证a^d mod n是否为1或n−1，以及序列a^(d×2^i) mod n中是否出现n−1；若所有a均通过则判为素数，否则为合数。
什么是美利坚强素数（Miller–Rabin）判定的核心逻辑
美利坚强素数不是标准数学名词，实际指的是用 Miller–Rabin 算法判定的“强伪素数”意义上的素数——即通过该概率性测试、被高度信任为素数的正整数。它不保证 100% 正确，但对 64 位整数，选对基底后可做到确定性判断。
关键点在于：Miller–Rabin 不是直接试除，而是基于费马小定理和二次探测原理。对奇数 n > 2，写成 n−1 = d × 2^r（d 为奇数），再对若干小整数 a（称为基底）验证：
① a^d mod n ≠ 1，且
② 对所有 i ∈ [0, r−1]，a^(d×2^i) mod n ≠ n−1
若对某个 a 同时满足①②，则 n 一定为合数；否则暂认为“可能为素数”。
64 位整数下如何选基底实现确定性判定
对 uint64_t 范围内的正整数（n ），已知只需测试固定几个基底即可 100% 判定素性，无需随机采样。这是实际工程中必须利用的优化。
- 若
n ，测试基底 <code>{2, 7, 61}足够（覆盖全部 32 位整数） - 若
n ，必须用 <code>{2, 325, 9375, 28178, 450775, 9780504, 1795265022}（共 7 个） - 注意：基底必须小于
n；若n恰等于某个基底（如n == 2），需提前特判 - 对
n == 2、n == 3等小素数，直接返回 true，避免模幂计算开销
快速模幂运算中容易溢出的坑
C++ 原生 long long 无法直接计算 a^d mod n（a、d、n 都接近 2^64），中间乘法会溢出。必须用 __int128（GCC/Clang 支持）或手写乘法取模。
立即学习“C++免费学习笔记（深入）”；
- 推荐优先用
__int128实现mulmod(a, b, m)：先转为__int128相乘，再取模 - 若编译器不支持
__int128（如 MSVC），必须用 O(log b) 的龟速乘（binary multiplication）：每次加法后都模m - 切忌写
(a * b) % m—— 即使a和b小于m，乘积也可能超2^64，导致未定义行为 - 注意：
mulmod(0, x, m)和mulmod(x, 0, m)必须返回 0，边界情况常被忽略
完整判定函数的关键结构与特例处理
一个健壮的 is_prime(n) 必须把“小值特判”、“偶数排除”、“分解 n−1”、“模幂循环”这几步严格分离，否则容易漏 case。
- 先处理
n → false；<code>n == 2→ true；n % 2 == 0→ false - 将
n−1拆解为d * 2^r：用 while 循环右移，记录r，d自动变为奇数 - 对每个基底
a： • 若a % n == 0（即a >= n且整除），跳过（但实际选基底时已确保a ，此步可省） • 计算 <code>x = powmod(a, d, n)• 若x == 1 || x == n−1，该基底通过，继续下一个 • 否则循环r−1次：更新x = mulmod(x, x, n)，若某次x == n−1则跳出内层循环 • 若内层循环结束仍未出现n−1，返回 false - 所有基底都通过，返回 true
最易错的是内层循环次数（应为 r−1 次，不是 r 次），以及 n−1 的表示——必须写成 n - 1，而非 -1（负数模运算结果不可靠）。
