C++如何判断一个正整数是否为强伪素数(基于不同底数的测试)-C++-PHP中文网

强伪素数是指对特定底数a通过miller-rabin测试但实际为合数的数；它依赖底数定义，如“n是以a=2为底的强伪素数”；miller-rabin测试通过检验a^d≡1或a^(d·2^r)≡−1(mod n)来判断素性，满足则为可能素数（即a-强伪素数候选）。

c++如何判断一个正整数是否为强伪素数(基于不同底数的测试)

什么是强伪素数？它和Miller-Rabin测试什么关系

强伪素数不是独立定义的“数类”，而是指：对某个特定底数 a，通过了Miller-Rabin素性测试但实际是合数的数。换句话说，它是针对某底数 a 的“漏判”结果。你无法脱离底数谈“强伪素数”——必须说“n 是以 a=2 为底的强伪素数”。

Miller-Rabin 测试本质是检查 n 是否满足：若 n 是素数，则对任意 a ∈ [2, n−2]，必有某种模幂结构成立（即 a^d ≡ 1 (mod n) 或存在某 r 使得 a^(d·2^r) ≡ −1 (mod n)）。不满足 → 合数；满足 → “可能素数”（即以 a 为底的强伪素数候选）。

手写Miller-Rabin核心逻辑：怎么实现单底数判断

关键在把 n−1 拆成 d × 2^s（d 为奇数），再计算 a^d mod n 及其反复平方。注意中间模幂必须用快速幂，且全程防溢出（尤其 n 接近 int64_t 上限时）。

用 uint64_t 存储所有中间值，避免负数和溢出
mul_mod(a, b, mod) 必须自己写：不能直接 a * b % mod，要用二分乘法或 __int128（若编译器支持）
对 n ，已知确定性底数集为 <code>{2, 325, 9375, 28178, 450775, 9780504, 1795265022}；但判断“是否为某底数的强伪素数”，只需测单个 a
若 n 是偶数或 ≤ 3，直接特判；a 必须满足 1 ，否则测试无效

bool is_strong_pseudoprime(uint64_t n, uint64_t a) {
    if (n uint64_t d = n - 1;
int s = 0;
while ((d & 1) == 0) {
    d >>= 1;
    s++;
}

uint64_t x = pow_mod(a, d, n); // 自实现的模幂
if (x == 1 || x == n - 1) return true;

for (int r = 1; r <p>}</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img
														src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a>
													<p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p>
												</div>
												<a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>

常见坑：为什么你测出来总是 false 或崩溃

最常踩的不是算法逻辑，而是底层运算安全问题：

pow_mod 若没处理 a ≥ n，会导致 a % n == 0，后续全为 0 —— 误判为合数（其实应先 a %= n）
mul_mod 直接 (a * b) % mod 在 a,b ~ 1e18 时必然溢出 —— __int128 是最快解法（GCC/Clang 支持），否则必须用 O(log b) 的倍增乘法
没排除 n 是完全平方数等小合数，导致 s=0 分支未覆盖；或 n=1、n=4 这类边界没单独返回
误以为“通过所有常用底数测试”就等于素数 —— 实际上 uint64_t 范围内存在对前 12 个底数都通过的合数（如 3186658578340311511），必须用完整确定性集合