强伪素数是指对特定底数a通过Miller-Rabin测试但实际为合数的数；它依赖底数定义，如“n是以a=2为底的强伪素数”；Miller-Rabin测试通过检验a^d≡1或a^(d·2^r)≡−1(mod n)来判断素性，满足则为可能素数（即a-强伪素数候选）。
什么是强伪素数？它和Miller-Rabin测试什么关系
强伪素数不是独立定义的“数类”，而是指：对某个特定底数 a，通过了Miller-Rabin素性测试但实际是合数的数。换句话说，它是针对某底数 a 的“漏判”结果。你无法脱离底数谈“强伪素数”——必须说“n 是以 a=2 为底的强伪素数”。
Miller-Rabin 测试本质是检查 n 是否满足：若 n 是素数，则对任意 a ∈ [2, n−2]，必有某种模幂结构成立（即 a^d ≡ 1 (mod n) 或存在某 r 使得 a^(d·2^r) ≡ −1 (mod n)）。不满足 → 合数；满足 → “可能素数”（即以 a 为底的强伪素数候选）。
手写Miller-Rabin核心逻辑：怎么实现单底数判断
关键在把 n−1 拆成 d × 2^s（d 为奇数），再计算 a^d mod n 及其反复平方。注意中间模幂必须用快速幂，且全程防溢出（尤其 n 接近 int64_t 上限时）。
- 用
uint64_t存储所有中间值，避免负数和溢出 -
mul_mod(a, b, mod)必须自己写：不能直接a * b % mod，要用二分乘法或__int128（若编译器支持） - 对
n ，已知确定性底数集为 <code>{2, 325, 9375, 28178, 450775, 9780504, 1795265022}；但判断“是否为某底数的强伪素数”，只需测单个a - 若
n是偶数或 ≤ 3，直接特判；a必须满足1 ，否则测试无效
bool is_strong_pseudoprime(uint64_t n, uint64_t a) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
if (a % n == 0) return false; // a 和 n 不互质，跳过或视为合数
<pre class='brush:php;toolbar:false;'>uint64_t d = n - 1;
int s = 0;
while ((d & 1) == 0) {
d >>= 1;
s++;
}
uint64_t x = pow_mod(a, d, n); // 自实现的模幂
if (x == 1 || x == n - 1) return true;
for (int r = 1; r < s; r++) {
x = mul_mod(x, x, n);
if (x == n - 1) return true;
}
return false; // 以 a 为底，n 是合数（不是强伪素数）}
立即学习“C++免费学习笔记（深入）”；
常见坑：为什么你测出来总是 false 或崩溃
最常踩的不是算法逻辑，而是底层运算安全问题：
-
pow_mod若没处理a ≥ n，会导致a % n == 0，后续全为 0 —— 误判为合数（其实应先a %= n） -
mul_mod直接(a * b) % mod在a,b ~ 1e18时必然溢出 ——__int128是最快解法（GCC/Clang 支持），否则必须用 O(log b) 的倍增乘法 - 没排除
n是完全平方数等小合数，导致s=0分支未覆盖；或n=1、n=4这类边界没单独返回 - 误以为“通过所有常用底数测试”就等于素数 —— 实际上
uint64_t范围内存在对前 12 个底数都通过的合数（如3186658578340311511），必须用完整确定性集合
验证已知强伪素数：比如 2047 对底数 2
2047 = 23 × 89，是经典例子。用上面函数跑 is_strong_pseudoprime(2047, 2) 应返回 true —— 它就是以 2 为底的强伪素数。
验证步骤：
n−1 = 2046 = 1023 × 2^1 → d=1023, s=1
算 2^1023 mod 2047：结果是 1（可验算），满足第一条件 → 返回 true
真正难的是反向找：给定 n，遍历 a 找哪些使它成为强伪素数。这没有捷径，只能暴力试 —— 但实践中几乎没人这么做，因为意义有限：你真正需要的是“确认素性”，而不是“找它骗过谁”。
