强伪素数是合数却通过以a为底的miller–rabin“强可能素数”检验的数；需满足1
什么是强伪素数？先看判定逻辑
强伪素数不是“伪素数”的加强版，而是针对 Miller–Rabin 测试中某个特定底数 a 的失败情况：一个合数 n 在以 a 为底的 Miller–Rabin 检验中“侥幸通过”，就称其为关于底数 a 的强伪素数。
判断的关键是把 n−1 写成 d × 2^s（其中 d 是奇数），然后检查以下两个条件是否**都不成立**：
pow_mod(a, d, n) == 1- 存在某个
r ∈ [0, s)，使得pow_mod(a, d * (1
如果都不成立，则 n 是关于 a 的强伪素数（即 Miller–Rabin 对它失效）；否则不是。
大整数运算必须用模幂（pow_mod）
C++ 标准库不支持任意精度整数，long long 最多撑到约 10¹⁸，远不够判断典型的大整数（比如 2048 位 RSA 模数）。你得用第三方库或自己实现——但无论如何，pow_mod 是核心，不能直接算 a^d 再取模（会溢出或超时）。
常见错误包括：
- 用
std::pow或递归幂函数，没做中间模运算 → 立刻溢出 - 没处理
a ≥ n的情况 → 应先做a %= n，且若结果为 0 则直接判定为合数（除非n == a） - 忽略
n是偶数或 ≤ 2 的边界 → 这些情况应提前返回，不进入强伪素数判定流程
示例片段（基于 __int128 或 boost::multiprecision::cpp_int）：
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
cpp
cpp_int pow_mod(cpp_int base, cpp_int exp, cpp_int mod) {
cpp_int res = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) res = (res * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return res;
}
如何分解 n−1 = d × 2^s
这步看似简单，但容易写错循环终止条件或漏掉 s == 0 的情形。实际只需反复除以 2，直到余数为奇数。
正确做法：
- 令
temp = n - 1 -
s = 0，whiletemp % 2 == 0：temp /= 2，s++ - 此时
d = temp，s就是幂次
注意：n 必须是奇合数才有意义（偶数直接排除），且 n > 2；若 n == 9，则 n−1 = 8 = 1 × 2³，所以 d = 1, s = 3 —— 这个分解直接影响后续循环范围。
完整判定函数怎么写（含常见坑点）
给定 n（大整数）和底数 a（通常 2 ≤ a n 是否为关于 a 的强伪素数：
- 先确认
n是奇合数（非质数、> 2、奇数）；若不知是否为合数，需额外用确定性算法（如 AKS 或小素数试除）预筛，否则“强伪素数”定义不成立 - 计算
d,s如上 - 算
x = pow_mod(a, d, n)；若x == 1 || x == n-1，则n不是关于a的强伪素数（检验通过） - 否则对
r = 1到s−1，依次算x = pow_mod(a, d * (1；若某次 <code>x == n−1，也说明检验通过 - 如果所有
r都没满足，且初始x != 1，那么n就是关于a的强伪素数
特别注意：1 在大整数场景下必须用大整数左移（如 <code>cpp_int(1) ），不能用 <code>int 位运算，否则 r > 63 就 UB。
真正难的不是逻辑，而是确保每一步都在模意义下安全、每处类型匹配、每个边界值（如 n=9, a=2）都经得起验证——这些细节一旦松懈，结果就不可信。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
