强伪素数是针对特定底数a和奇合数n的相对判定结果：若n为奇合数且满足以a为底的Miller-Rabin通过条件，则称n是以a为底的强伪素数；函数必须带a参数，n−1需正确分解为d×2^r，模幂须防溢出，二次探测中遇非法1（前驱非n−1）即判合数。
什么是强伪素数，不是“判断素数”
强伪素数不是一种独立的数类，而是对某个底数 a 和某个合数 n 的相对判定结果：若 n 是合数，且满足 Miller-Rabin 测试中以 a 为底的“通过条件”，就称 n 是以 a 为底的强伪素数。
这意味着你不能只写一个 is_strong_pseudoprime(n)——必须指定底数 a，函数签名应为 bool is_strong_pseudoprime(uint64_t n, uint64_t a)。漏掉 a 参数，逻辑就错了。
-
n必须是奇合数（即n > 2、n % 2 == 1、且非素数），否则直接返回false -
a必须满足1 且 <code>gcd(a, n) == 1；若a % n == 0或a >= n，测试无意义，跳过或返回false - 常见误判：把
is_prime(n)和is_strong_pseudoprime(n, a)混用——前者输出“可能是素数”，后者输出“这个合数骗过了底数a”
怎么分解 n−1 = d × 2^r，不能靠循环除2硬算
这是整个测试的前置步骤，出错会导致后续所有模幂和二次探测全错。例如 n = 2047，n−1 = 2046，正确分解是 d = 1023, r = 1；若算成 d = 511, r = 2，就会把真强伪素数 2047 判为合数。
- 用位运算替代除法：
d = n - 1; r = 0; while ((d & 1) == 0) { d >>= 1; r++; } - 别用
d /= 2——对大整数虽可行，但位运算更稳、更快，且避免有符号右移陷阱 - 特判
n == 2或n为偶数时，不进入此步；强伪素数定义要求n是奇合数，偶数直接排除
模幂计算必须防溢出，否则 pow_mod(a, d, n) 结果全错
对 64 位整数，a 和 d 都可能接近 2⁶⁴，a^d 远超 uint64_t 表示范围。直接用 std::pow 或朴素乘法再取模，中间值溢出后结果不可信。
立即学习“C++免费学习笔记（深入）”；
- 必须实现带防溢出乘法的快速幂：先写
uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t mod)，用加法模拟乘法或借助__int128（GCC） - 若用
__int128，写法是return (static_cast<__int128>(a) * b) % mod;</__int128>；不用则需手写加法倍增版本 -
pow_mod内部调用mul_mod，不能出现(a * b) % mod这种裸乘 - 测试点：
n = 3215031751（已知合数），用底数a = 2，若模幂溢出，会错误返回true
二次探测阶段最容易漏掉“中途得 1 却没前驱是 n−1”的合数证据
Miiller-Rabin 的关键不只是看最后是否等于 n−1，而是检查平方序列中是否出现非法的 1：若某次 x == 1，但上一次 x != n−1，说明 n 有非平凡平方根，必为合数。
- 标准流程：算出
x = pow_mod(a, d, n)后，先检查x == 1 || x == n-1→ 若成立，本轮通过 - 否则，执行
r−1次迭代：x = mul_mod(x, x, n)，每次检查x == n−1 - **关键细节**：若某次迭代后
x == 1，但上一轮x != n−1，立刻返回false（这是合数铁证） - 很多人只检查
n−1，忽略这个 1 的来源合法性，导致把 Carmichael 数如561在某些底数下误判为强伪素数
实际中最容易被忽略的，是“强伪素数”这个概念本身依赖底数 a 的严格绑定——换一个 a，同一个 n 可能从强伪素数变成裸露的合数。写代码时若把 a 写死或随机化不当，结论就失去可复现性。
