Rabin-Miller素性测试处理6位及以上数字崩溃问题排查

• 程序处理5位及以下数字时可正常运行，处理6位及以上数字时触发崩溃
• 你提到的Rabin-Miller固有伪素数误判问题可通过增加测试轮次/测试基解决，但当前崩溃属于代码实现错误，和算法本身局限无关

故障根因 #

1. 核心问题：整数溢出+pow函数滥用
   • 代码中使用的pow()是浮点运算函数，返回值为double类型，计算大指数时精度会严重丢失。当计算pow(2, primenumber_mod)时，6位数字对应的primenumber_mod最高接近10万，2的10万次方远超过double的精确表示范围，强转为int时会得到无意义的垃圾值，触发未定义行为。
   • 32位int类型最大存储值为2^{31-1=2147483647，只要数值大于46340，平方结果就会超过int上限。6位数字最小值为100000，平方结果达10}10，远超int存储范围，溢出后会出现负值、随机值，甚至直接触发内存访问错误导致崩溃。
2. 算法逻辑缺失
   • 拆分n-1 = d*2^s时只计算了d，没有记录s的值，循环平方校验的次数没有按算法要求用s限制，反而硬编码40次上限，不符合Rabin-Miller标准流程。
   • prime变量存在未初始化返回风险：如果命中variable_1 ==1 || variable_1 ==-1分支，prime未被赋值就被return，会返回栈上的随机垃圾值。
   • 硬编码排除43405、27905属于补丁式写法，无法从根源解决伪素数误判问题。
3. 其他问题
   • primeGenerator随机数范围计算错误，原逻辑生成的上限为999000，遗漏了999001~999999的6位区间。
   • testPrimeSafe校验函数从2遍历到n本身，性能极差，且没有利用“合数最小因子不超过自身平方根”的特性做优化。

修复方案 #

替换浮点pow为自定义的模幂（快速幂）运算，所有中间计算值用64位long long类型存储避免溢出；补全Rabin-Miller标准逻辑，选择合适的测试基（对小于2^32的数，测试2、3、5、7、11这几个基即可做到100%判定准确，完全覆盖6位数字场景）。

修复后的完整代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

// 模幂运算：计算 (base^exp) % mod，全程取模避免大数溢出
long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return result;
}

bool testPrime(long long n) {
    // 边界值快速处理
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0) return false;

    // 拆分n-1为 d * 2^s
    long long d = n - 1;
    int s = 0;
    while (d % 2 == 0) {
        d /= 2;
        s++;
    }

    // 测试固定基，6位数字场景下无伪素数误判
    int bases[] = {2, 3, 5, 7, 11};
    for (int a : bases) {
        if (a >= n) continue;
        long long x = mod_pow(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool pass = false;
        for (int j = 1; j < s; j++) {
            x = (x * x) % n;
            if (x == n - 1) {
                pass = true;
                break;
            }
        }
        if (!pass) return false;
    }
    return true;
}

int primeGenerator()
{
    // 修正随机数范围，覆盖完整6位区间100000~999999
    int number = rand() % 900000 + 100000;
    while (!testPrime(number))
    {
        number = rand() % 900000 + 100000;
    }
    return number;
}

bool testPrimeSafe(long long number)
{
    if (number <= 1) return false;
    if (number <= 3) return true;
    if (number % 2 == 0) return false;
    // 优化：只遍历到sqrt(n)，步长设为2跳过偶数，性能提升数百倍
    for (long long i = 3; i * i <= number; i += 2)
    {
        if (number % i == 0)
        {
            return false;
        }
    }
    return true;
}

void testTestPrime()
{
    for (int i = 0; i < 10000; i++)
    {
        int prime = primeGenerator();
        if (testPrimeSafe(prime))
        {
            std::cout << "\e[32;42mSUCCESS :: " << prime << "\e[0m\n";
        }
        else
        {
            std::cout << "\e[48;5;196;1m*EVIL MORTY THEME PLAYING* :: " << prime << "\e[0m\n";
        }
    }
}

int main()
{
    srand(time(NULL));
    testTestPrime();
    return 0;
}

内容的提问来源于stack exchange，提问作者Anton Zange