C++如何判断一个数是否为强伪素数（Strong Pseudoprime）-C++-PHP中文网

强伪素数是合数却通过miller–rabin测试中某底数a的“强可能素数”检验；需满足1

c++如何判断一个数是否为强伪素数（strong pseudoprime）

什么是强伪素数？先看判定逻辑

强伪素数不是素数，但在 Miller–Rabin 测试中对某个底数 a 通过了“强可能素数”检验。换句话说：它骗过了某一轮 Miller–Rabin 的确定性检查。判断一个合数 n 是否为以 a 为底的强伪素数，核心是执行 Miller–Rabin 的分解步骤，并验证是否满足“强可能素数”的条件——即使它是合数。

关键前提：必须满足 1 ，且 <code>gcd(a, n) == 1；否则直接判定为非强伪素数（因为 a 和 n 不互质，a 就是 n 的真因子）。

怎么用 C++ 实现强伪素数判定？重点在模幂和分解

Miller–Rabin 的核心是把 n−1 写成 d × 2^r 形式（d 为奇数），然后计算 pow_mod(a, d, n)，再反复平方看是否出现 ≡ 1 或 ≡ n−1（即 −1 mod n）。

常见错误：

直接用 std::pow 导致溢出或精度丢失 → 必须手写或调用 mod_pow
忘记处理 n 是偶数或小素数（如 2、3、5）→ 应提前排除或特判
没检查 gcd(a, n) != 1 就继续计算 → 此时 n 显然不是强伪素数（因有非平凡因子）

实操建议：

用 long long 时，模乘需防溢出：用 __int128（GCC）或拆分乘法（如俄罗斯农民乘法）
r 最多约 64（对 64 位整数），循环上限可设为 64 次
若 mod_pow(a, d, n) == 1 || mod_pow(a, d, n) == n-1，则 n 是以 a 为底的强可能素数；但要确认它是合数，才叫强伪素数 → 所以你得额外有个合数判定（比如试除到 sqrt(n)，或用已知小素数表筛）

示例片段（简化版，忽略大数模乘细节）：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

bool is_strong_pseudoprime(long long n, long long a) {
    if (n = n) return false;
    if (gcd(a, n) != 1) return false; // 关键！不互质直接否决
    if (is_prime(n)) return false;    // 真素数不算强伪素数
<pre class="brush:php;toolbar:false;">long long d = n - 1;
int r = 0;
while (d % 2 == 0) { d /= 2; r++; }

long long x = mod_pow(a, d, n);
if (x == 1 || x == n-1) return true;

for (int i = 1; i <p>}</p>

为什么有些数对多个底数都是强伪素数？比如 Carmichael 数

Carmichael 数（如 561、1105）对所有与它互质的 a 都满足费马小定理，但它们不全是强伪素数——只有部分底数能让它们通过 Miller–Rabin 的强检验。

例如：561 对 a = 2 是强伪素数，但对 a = 3 不是（会暴露为合数）。这是因为 Miller–Rabin 比费马测试更强：它要求序列中某个平方根是 −1 mod n，而 Carmichael 数不一定满足这个链式条件。

性能影响：

单次判定复杂度是 O(log²n)（含模幂）
若你要查某个 n 是否是“对前 k 个素数都成立的强伪素数”，就得跑 k 次，别忘了每次都要做 gcd 和模幂
对于 n > 2^64，标准 long long 不够，必须上 __int128 或 big integer 库（如 Boost.Multiprecision）