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

强伪素数是满足miller-rabin测试中某底数a下通过素性检验的合数；如2047（23×89）是以2为底的强伪素数，25是以7为底的强伪素数，且其存在依赖底数，无全局强伪素数。

c++如何判断一个数是否为强伪素数

强伪素数不是标准库函数能直接判断的，必须手动实现 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。

核心是写一个 is_strong_pseudoprime(n, a) 函数，它不判断 n 是否为素数，只回答：“给定 n 和底数 a，n 是否通过 Miller-Rabin 的强检验？”

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 <h3>容易踩的坑有哪些？</h3><p>实际写的时候，这几个点最常导致误判或崩溃：</p>

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，且中间步骤满足强条件