强伪素数测试必须指定底数a，n需为奇合数且满足miller-rabin条件才称以a为底的强伪素数；常见错误包括参数混淆、a与n不互质、忽略奇合数前提及用除法分解n-1；正确应使用位运算提取d和r。
强伪素数测试不是独立函数，必须带底数 a 参数
“判断是否通过强伪素数测试”本身不是一个完整问题——is_strong_pseudoprime(n) 这种写法是错的。强伪素数是相对概念：只有当 n 是奇合数，且对某个特定底数 a 满足 Miller-Rabin 的“通过条件”，才称 n 是以 a 为底的强伪素数。
常见错误包括：
- 把
is_prime(n)和is_strong_pseudoprime(n, a)混用，前者输出“可能是素数”，后者只在已知n是合数的前提下才有意义 - 传入
a >= n或a % n == 0，此时gcd(a, n) != 1，测试无效，应直接返回false - 忽略
n必须为奇合数的前提：若n == 2、n为偶数、或n实际是素数，都不构成强伪素数
n-1 = d × 2^r 分解必须用位运算，不能除法硬算
对大整数（如 boost::multiprecision::cpp_int），n-1 的分解不能靠 while (d % 2 == 0) { d /= 2; r++; } ——除法慢、易溢出、且对符号/边界处理不稳。
正确做法是：
- 令
d = n - 1，r = 0 -
while ((d & 1) == 0) { d >>= 1; r++; }（cpp_int支持&和>>=） - 结束时的
d就是奇数部分，不用再算(n-1) / (1 - 特判：
n为偶数或n 时直接跳过，强伪素数定义不覆盖这些情况
模幂必须走 mul_mod，(a * b) % n 在大数下必然失效
标准类型如 uint64_t 做 a * b 会溢出；cpp_int 虽能存大数，但裸乘再模效率低、中间值可能达 O(n²)，拖慢整个测试。
必须实现防溢出的乘法：
- 若用
__int128（GCC）：return (static_cast<__int128>(a) * b) % mod;</__int128> - 否则手写加法倍增版
mul_mod(a, b, mod)，每次加完立即% mod -
pow_mod(a, d, n)内部每一步乘法都调用mul_mod，不能出现(x * y) % n -
a入参前先a %= n，避免无谓的大数平方
二次探测阶段要捕获“非法 1”，不是只看最后结果
Miiller-Rabin 的关键证据不在最终值，而在平方序列中是否出现 x == 1 但前驱 pre != n-1 且 pre != 1 ——这说明 n 有非平凡平方根，必为合数。
实操要点：
- 记录上一次值
pre，每次x = mul_mod(x, x, n)后检查：if (x == 1 && pre != 1 && pre != n-1) return false; - 循环最多跑
r次（即从a^d开始，平方r次），别漏掉第 0 次（初始x == a^d mod n） - 若某次
x == n-1，该轮测试通过，跳出内层循环 - 测试点：
n = 2047（以a = 2为底的强伪素数），若漏检非法 1，会误判为合数
真正难的不是写对逻辑，而是让 mul_mod 和位分解在 cpp_int 上不出隐式转换 bug——比如没加 #define BOOST_MULTIPRECISION_CPP_INT_BACKEND_NO_ET，表达式模板会让 a * b % n 看似正常，实则中间生成临时对象导致性能崩坏或结果错乱。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
