c++ - C++ 中的 Miller-Rabin 素数测试问题

Question

我一直在尝试实现 the algorithm from wikipedia虽然它从不将合数输出为质数，但它会将大约 75% 的质数输出为合数。

最多 1000 它为我提供了这个素数输出:

3, 5, 7, 11, 13, 17, 41, 97, 193, 257, 641, 769

据我所知，我的实现与伪代码算法完全相同。我逐行调试它，它产生了所有预期的变量值(我一直在跟踪我的计算器)。这是我的功能:

bool primeTest(int n)
{
    int s = 0;
    int d = n - 1;

    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }

    // this is the LOOP from the pseudo-algorithm
    for (int i = 0; i < 10; i++)
    {
        int range = n - 4;
        int a = rand() % range + 2;
        //int a = rand() % (n/2 - 2) + 2;
        bool skip = false;
        long x = long(pow(a, d)) % n;

        if (x == 1 || x == n - 1)
            continue;

        for (int r = 1; r < s; r++)
        {
            x = long(pow(x, 2)) % n;

            if (x == 1)
            {
                // is not prime
                return false;
            }
            else if (x == n - 1)
            {
                skip = true;
                break;
            }
        }

        if (!skip)
        {
            // is not prime
            return false;
        }
    }

    // is prime
    return true;
}

如有任何帮助，我们将不胜感激:

编辑:这是整个程序，按照你们的建议进行了编辑——现在输出更加糟糕:

bool primeTest(int n);

int main()
{
    int count = 1;     // number of found primes, 2 being the first of course
    int maxCount = 10001;
    long n = 3;
    long maxN = 1000;
    long prime = 0;

    while (count < maxCount && n <= maxN)
    {
        if (primeTest(n))
        {
            prime = n;
            cout << prime << endl;
            count++;
        }

        n += 2;
    }

    //cout << prime;
    return 0;
}

bool primeTest(int n)
{
    int s = 0;
    int d = n - 1;

    while (d % 2 == 0)
    {
        d /= 2;
        s++;
    }

    for (int i = 0; i < 10; i++)
    {
        int range = n - 4;
        int a = rand() % range + 2;
        //int a = rand() % (n/2 - 2) + 2;
        bool skip = false;
        //long x = long(pow(a, d)) % n;
        long x = a;
        for (int z = 1; z < d; z++)
        {
            x *= x;
        }

        x = x % n;

        if (x == 1 || x == n - 1)
            continue;

        for (int r = 1; r < s; r++)
        {
            //x = long(pow(x, 2)) % n;
            x = (x * x) % n;

            if (x == 1)
            {
                return false;
            }
            else if (x == n - 1)
            {
                skip = true;
                break;
            }
        }

        if (!skip)
        {
            return false;
        }
    }

    return true;
}

现在素数的输出，从 3 到 1000(和以前一样)是:

3, 5, 17, 257

我现在看到 x 变得太大了，它变成了一个垃圾值，但直到我删除了“% n”部分我才看到这一点。

Answer 1

错误的可能来源是对 pow 函数的两次调用。中间结果会很大(特别是对于第一次调用)并且可能会溢出，从而导致错误。你应该看看 modular exponentiation维基百科上的主题。