米勒-拉宾测试在c++中不能直接用long long，因为其最大值约10¹⁸远小于rsa等场景所需的几百至上千位大整数；必须借助boost.multiprecision::cpp_int等高精度库，并使用powm进行模幂运算，严格在每步中间结果做模约减以避免溢出或oom。
米勒-拉宾测试在C++里为什么不能直接用 long long
因为 long long 最大只能存约 10¹⁸，而米勒-拉宾常用于判断几百位甚至上千位的整数是否为素数——比如 RSA 密钥生成中的候选大素数。这时候必须用大整数库或手写模幂运算，否则连数都存不下，更别说做 mod 运算了。
常见错误是试图把字符串形式的大数 std::string 直接转成 unsigned long long，结果溢出后得到 0 或随机值，后续所有测试都毫无意义。
- 真正可用的方式只有两种：用现成高精度库（如
Boost.Multiprecision或OpenSSL的BIGNUM），或自己实现基于字符串/数组的模幂和模乘 - 如果只是临时验证、不追求极致性能，
Boost.Multiprecision::cpp_int是最省心的选择，它支持任意精度且重载了%、*、+等运算符 - 注意
cpp_int默认不启用模优化，大数模幂（如a^b % n）若直接写powm(a, b, n)会慢得不可接受；必须手写快速幂+逐位模乘，或调用boost::multiprecision::powm
如何用 boost::multiprecision::cpp_int 实现米勒-拉宾
核心是把标准算法里的整数运算全部替换为 cpp_int 版本，并确保中间结果始终做模约减。关键步骤不是“怎么写循环”，而是“在哪一步做模”——漏掉一次模，就可能触发 OOM 或计算错误。
下面这段代码能跑通 200 位以内的数（更高位需确认 Boost 编译时启用了 GMP 后端）：
#include <boost>
#include <random><p>using namespace boost::multiprecision;</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>
<p>bool miller_rabin(const cpp_int& n, int rounds = 25) {
if (n </p>
<pre class="brush:php;toolbar:false;">// 分解 n-1 = d * 2^r
cpp_int d = n - 1;
int r = 0;
while (d % 2 == 0) {
d /= 2;
r++;
}
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<long long> dis(2, std::min(static_cast<long long>(n-2), 1000000LL));
for (int i = 0; i = n - 1) a = 2; // fallback
cpp_int x = powm(a, d, n); // 必须用 powm！不是 std::pow
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int j = 1; j <p>}</p>
-
powm(a, d, n)是 Boost 提供的安全模幂函数，内部做了 Montgomery 优化；千万别用pow(a,d)%n，中间结果会爆炸 - 随机基
a的范围要控制在[2, n-2]，但对超大n，uniform_int_distribution无法直接生成，所以退而取min(n-2, 10^6)—— 对于安全用途，建议改用cpp_int自带的随机生成器（cpp_int::backend().generate_canonical） - 轮数
rounds=25对 2048-bit 数足够（错误率 2^p-1 的梅森数候选），可适当减少
不用 Boost 怎么办？手写模幂的三个硬约束
如果你被要求禁用第三方库，或者目标平台没有 Boost，那必须自己实现模幂。但别从零开始写大整数——先用 std::vector<uint64_t></uint64_t> 存数字（低位在前），再实现三件事：
- 加法、乘法、比较（至少要支持
和 <code>==） - 除以 2（用于分解
n-1）和模 2 判断（用于找r） -
modmul(a, b, m)和modpow(a, b, m)，其中modmul必须用俄罗斯农民乘法 + 逐位累加 + 中间模m，否则a*b会溢出uint64_t
最容易被忽略的是：即使你只测一个数，也要对每个随机基 a 单独做完整模幂；不能复用中间状态，也不能跳过某次 x == n-1 的检查——米勒-拉宾的确定性依赖于每一轮独立验证。
误报和漏报的真实风险点在哪里
米勒-拉宾是概率算法，但实际使用中“误判”几乎只发生在两类情况：
- 选了坏的随机基：比如对
n = 2047（= 23 × 89），用a = 2就会错误判定为素数（它是第一个以 2 为伪证的合数）；这就是为什么需要多轮 + 随机基 - 实现错误导致模运算失效：例如在
modmul里忘了对中间和做% m，结果数值失控，最终x值完全失真 - 没处理边界：
n=1、n=2、n=4这些小值必须单独返回，否则算法里除以 2 会死循环或崩溃
真正危险的不是“它偶尔错”，而是“你以为它没错，但它在某个特定输入上恒定出错”——比如你的随机数生成器始终返回同一个值，或者 powm 在 n 为完全平方数时行为异常。上线前务必用已知 Carmichael 数（如 561、41041）和前 100 个素数交叉验证。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
