强伪素数是满足Miller-Rabin测试中某底数a下通过素性检验的合数；如2047（23×89）是以2为底的强伪素数，25是以7为底的强伪素数，且其存在依赖底数，无全局强伪素数。
强伪素数不是标准库函数能直接判断的，必须手动实现 Miller-Rabin 测试，并注意底数选取和边界处理。
什么是强伪素数？
一个合数 n，对某个底数 a（满足 1 且 <code>gcd(a, n) == 1），通过了 Miller-Rabin 素性测试的“强伪证”步骤，就称 n 是以 a 为底的强伪素数。它不是真素数，但骗过了该轮测试。
常见误区：误以为“强伪素数 = 某个固定集合”，其实它是相对概念——依赖底数 a 和被测数 n。例如 2047 是以 2 为底的强伪素数，因为 2^2046 ≡ 1 (mod 2047)，且满足强检验条件，但 2047 = 23 × 89。
如何用 C++ 实现强伪素数判定？
核心是写一个 is_strong_pseudoprime(n, a) 函数，它不判断 n 是否为素数，只回答：“给定 n 和底数 a，n 是否通过 Miller-Rabin 的强检验？”
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 先特判：
n必须是奇合数（n > 2且非素数），否则直接返回false；a必须满足1 且 <code>gcd(a, n) == 1，否则无定义 - 将
n−1写成d × 2^s形式（d为奇数） - 计算
x = pow_mod(a, d, n)（模幂，防止溢出） - 若
x == 1 || x == n−1，本轮通过，返回true - 否则循环
s−1次：更新x = (x * x) % n，若某次x == n−1，返回true - 全部失败则返回
false
示例关键片段：
bool is_strong_pseudoprime(long long n, long long a) {
if (n < 4 || n % 2 == 0 || n == 1) return false;
if (gcd(a, n) != 1) return false; // 底数必须与 n 互质
long long d = n - 1;
int s = 0;
while (d % 2 == 0) { d /= 2; s++; }
long long x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) return true;
for (int i = 1; i < s; i++) {
x = mul_mod(x, x, n); // 防止 long long 溢出的乘法取模
if (x == n - 1) return true;
}
return false;
}
容易踩的坑有哪些？
实际写的时候，这几个点最常导致误判或崩溃：
-
pow_mod和mul_mod必须手写，不能用std::pow或裸乘——C++ 原生运算会溢出。尤其mul_mod(a, b, mod)要用类似“二进制拆分 + 加法取模”的方式模拟大数乘法 - 没做
gcd(a, n) == 1检查：若a和n不互质（比如n=9, a=3），pow_mod可能返回 0，后续判断失效 - 忽略
n必须是合数的前提：如果传入的是真素数（如n=5, a=2），函数也会返回true（因为它确实通过测试），但这不是“强伪素数”，而是“真素数”。所以调用前应先用确定性方法（如试除法到 √n）确认n是合数 - 底数范围错误：标准定义要求
1 。用 <code>a=1总是通过，用a=n未定义，用a>n需先取模，但取模后可能破坏互质性
哪些数是经典强伪素数？
调试时可拿已知案例验证逻辑是否正确：
-
2047是以2为底的强伪素数（2047 = 23 × 89） -
121不是以3为底的强伪素数（gcd(3,121)=1，但测试失败）；但它以2为底是强伪素数？不，121 = 11²，实际is_strong_pseudoprime(121, 2)返回false—— 这说明不能凭经验猜测，必须实测 -
25是以7为底的强伪素数：验证7^24 mod 25 == 1，且中间步骤满足强条件
真正难的不是写对单次判断，而是理解：强伪素数永远依附于底数存在，没有“全局强伪素数”这种东西；Miller-Rabin 的可靠性，正来自多个不同底数联合测试后，强伪素数密度急剧下降。
