首页 > 编程语言 >C++判断正整数是否通过Miller-Rabin强伪素数测试

C++判断正整数是否通过Miller-Rabin强伪素数测试

来源：互联网 2026-07-11 07:59:05

C++标准库未提供强伪素数测试函数，需手动实现Miller-Rabin算法。该算法为概率性，通过测试仅表示未在当前底数下被证伪。实现需分解n-1为d×2^r，采用快速幂与防溢出模乘。对64位整数，选定固定底数集可实现确定性判定。

在C++中进行素性判定时，很多人下意识会去找一个叫is_strong_pseudoprime的函数，但标准库（包括、）里并没有这东西。换句话说，你得自己动手实现Miller-Rabin测试逻辑，要么借助第三方数学库（比如Boost.Multiprecision或GMP绑定），但即便如此，核心的测试流程还是得手动来。关键点在于：Miller-Rabin本身是个概率性算法——对某底数a，它判断n是不是以a为底的强伪素数；所谓“通过测试”，只是对某个或某组a，n没暴露合数特征，这不等于它就是素数，只是没被当前底数证伪而已。

长期稳定更新的攒劲资源： >>>点此立即查看<<<

Miller-Rabin 测试中，`is_strong_pseudoprime` 不是标准库函数

标准 C++ 库（包括、）不提供任何素性判定函数，更没有叫 is_strong_pseudoprime 的内置函数。你必须自己实现 Miller-Rabin 测试逻辑，或借助第三方数学库（如 Boost.Multiprecision 或 GMP 绑定），但后者仍需手动调用测试流程。

关键点在于：Miller-Rabin 本身是一个概率性算法，它对给定底数 a 判断 n 是否为以 a 为底的强伪素数；所谓“通过测试”，是指对某个或某组 a，n 没暴露出合数特征——但这不等于它是素数，只是没被当前底数证伪。

手动实现时，核心是分解 `n1` 为 `d × 2^r`

这是所有 Miller-Rabin 实现的第一步，也是最容易写错的地方：指数 r 必须从最大可能值开始算，不能简单右移计数后就停。例如 n = 13 → n1 = 12 = 3 × 2^2，这里 d = 3，r = 2。

用循环不断除以 2，直到 n1 变成奇数，记录除法次数得到 r，余下值即为 d
务必检查输入 n 是否 ≤ 2：直接返回 false（1 不是素数，2 是素数但需单独处理）
对小整数（如 n < 64），可硬编码已知素数表跳过测试，避免误判（比如 n=4 在任意底数下都立刻失败，但代码若没前置检查，可能在幂运算中间出错）

模幂运算 `mod_pow(a, d, n)` 必须用快速幂 + 模乘防溢出

对 32 位或 64 位整数，a^d mod n 直接计算会溢出。C++ 中没有原生大整数，所以 mod_pow 必须自己写，并在每次乘法后立即取模。更关键的是：中间乘法（如 x * y）本身也可能溢出，尤其当 n 接近 UINT64_MAX 时。

使用 uint64_t 类型承载中间结果
乘法部分用 __int128（GCC/Clang 支持）或拆位模拟（如 binary multiplication with mod）来避免溢出

若编译环境不支持 __int128，且 n 可能 > 10^12，则必须引入安全模乘函数，例如：

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m) {    uint64_t res = 0;    a %= m;    while (b) {        if (b & 1) res = (res + a) % m;        a = (a << 1) % m;        b >>= 1;    }    return res;}

确定底数集合决定确定性还是概率性

对 uint64_t 范围内的正整数（n < 2^64），已知一组固定底数即可做到确定性判定：若 n 对所有这些 a 都通过测试，则 n 必为素数。这不是经验猜测，而是数学证明结果。

常用确定性底数集：{2, 325, 9375, 28178, 450775, 9780504, 1795265022}（适用于 n < 2^64）
若只用 a = 2，则只能可靠判断 n < 2047；只用 a = 2,3，上限是 1373653 —— 超出就可能漏判合数
对每个 a，先检查 gcd(a, n) != 1：若成立，说明 n 显然不是素数（除非 a == n，但 a < n 时可直接返回 false）