C++中的米勒-拉宾素性检验问题

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主题。

Answer 2

问题的根源可能在这里：

x = long(pow(x, 2)) % n;

来自C标准库的pow适用于浮点数，所以如果你只想计算模n的幂，那么使用它是一个非常糟糕的想法。解决方案非常简单，只需手工将数字平方即可：

x = (x * x) % n