C++如何判断一个正整数是否通过了强伪素数测试（Miller-Rabin判定）-C++-PHP中文网

c++标准库不提供is_strong_pseudoprime函数，需手动实现miller-rabin测试：先特判n≤2，再分解n−1=d×2^r，用安全模幂和确定性底数集（如{2,325,…}）进行判定。

c++如何判断一个正整数是否通过了强伪素数测试（miller-rabin判定）

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

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

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

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

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

C++

"空空如也"

下载

用循环不断除以 2，直到 n−1 变成奇数，记录除法次数得到 r，余下值即为 d
务必检查输入 n 是否 ≤ 2：直接返回 false（1 不是素数，2 是素数但需单独处理）
对小整数（如 n ），可硬编码已知素数表跳过测试，避免误判（比如 <code>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;
    }
    return res;
}