强伪素数是满足Miller-Rabin强检验条件的合数；即n为奇合数、1<a<n且gcd(a,n)=1，将n−1写成d×2^r（d为奇数），并满足a^d≡1或a^(d·2^i)≡−1(mod n)（0≤i<r）。
什么是强伪素数？先看判定逻辑
强伪素数（Strong Pseudoprime）是针对某个底数 a 的合数 n，它通过了 Miller-Rabin 素性测试的“强检验”步骤，却仍不是素数。换句话说：它骗过了这个更严格的测试。
判断一个正整数 n 是否为某个底数 a 的强伪素数，必须满足三个前提：
-
n是奇合数（即n > 2且非素数） 1 ，且 <code>gcd(a, n) == 1- 在 Miller-Rabin 的分解形式
n−1 = d × 2^r下，满足：a^d mod n == 1，或者存在某个i ∈ [0, r)使得a^(d×2^i) mod n == n−1
怎么快速分解 n−1 成 d × 2^r？
这是 Miller-Rabin 的基础预处理，不能出错。
n−1 反复除以 2，直到结果为奇数，记录除的次数就是 r，剩下的奇数就是 d。
立即学习“C++免费学习笔记（深入）”；
int d = n - 1;
int r = 0;
while ((d & 1) == 0) {
d >>= 1;
r++;
}
常见错误：
- 用
d % 2 == 0判断奇偶但没及时更新d，导致死循环 - 把
r初始化成 1 或漏加，导致后续幂次计算错位 - 对
n == 2或偶数n直接套用——强伪素数定义要求n是奇合数，n == 2或偶数直接排除
模幂计算怎么写才不出错？
必须用快速模幂（mod_pow），否则 a^d mod n 会溢出或超时。
long long mod_pow(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) res = (__int128)res * base % mod;
base = (__int128)base * base % mod;
exp >>= 1;
}
return res;
}
关键点：
- 用
__int128防止中间乘法溢出（GCC 支持；若不可用，需用汇编或分段模乘） - 每次乘前都
% mod，但不能只对最终结果取模 - 底数
base初始就取模，避免后续溢出放大 - 不要用
pow()或std::pow——它们是浮点函数，不适用于大整数模运算
完整判断流程：三步缺一不可
给定正整数 n 和底数 a，要确认 n 是否为以 a 为底的强伪素数：
- 先检查
n是否为奇合数：若n 或为偶数或为素数（可用试除到 <code>sqrt(n)快速判小数），直接返回 false - 计算
d和r（如上） - 计算
x = mod_pow(a, d, n)；若x == 1 || x == n-1，进入下一步；否则循环i = 1到r-1，每次x = mod_pow(x, 2, n)，看是否出现x == n-1 - 若上述任一条件满足，且已确认
n是合数，则它是a-强伪素数；否则不是
最容易被忽略的一点：很多人只实现 Miller-Rabin 的“通过测试”逻辑，却忘了最后一步——必须额外验证 n 确实是合数。否则，素数也会满足强检验条件，但它不是强伪素数。
