如何确定一个极大的数字是否为质数？

Question

我正在尝试计算以下形式的数字（一些例子）：2 ^ 7 - 1，2 ^ 31 - 1，2 ^ 127 - 1等等。

这不是一道作业题，我只是在研究质数，但是有很多信息对我来说都有些难以理解（傅里叶变换）。最初，我只是使用了类似于以下函数：

public static bool IsPrime(int candidate)
{
    if ((candidate & 1) == 0)
    {
        return candidate == 2;
    }

    for (int i = 3; (i * i) <= candidate; i += 2)
    {
        if ((candidate % i) == 0)
        {
            return false;
        }
    }

    return candidate != 1;
}

当数字变得太大时，那种方法就行不通了。我还查阅了埃拉托斯特尼筛法，但显然只适用于规模较小的数字。

澄清一下，我不是要编写一个程序来查找质数，而是要确定给定的数字是否为质数。我正在研究.NET Framework中的BigInteger结构，如果我能写出一个足够高效的算法（即使需要几天时间），它看起来很有前途。

我不确定在这种情况下数学证明是否更好，但与编程相比，我对该领域的知识不多，但如果有一种专门针对这种数字的证明，那肯定值得研究。

谢谢。

- Ryan Peschel

---

这里有一个维基百科的概述：http://en.wikipedia.org/wiki/Primality_test。 - David Heffernan

Mersenne primes 还提供了关于这种特定形式的质数 (2^p-1) 的信息。 - Mat

寻找大质数是一项持续的科学努力，新发现的质数会获得奖励。要证明一个“极其”大的数字是质数需要超级计算机和可能还需要一支数学家团队。使用.NET代码在日常硬件上运行解决问题的实际限制可能会比迄今为止发现的最大质数要低得多。 - Adam Ralph

请参考http://www.ellipsa.eu/public/primo/primo.html，例如。 - Dr. belisarius

已知的梅森素数非常少，你最好列出它们所有，因为你几乎肯定不会发现任何新的，它们非常难找。 - harold

Answer 1

事实上，因数分解是一项重要的任务。它的复杂性是现代密码学的基础。

根据你所处理的数字大小不同，你可以获取到所有小于该数字平方根的质数列表。这种方式明显比每次加2来检查更加高效。但问题在于如何获取如此大的列表。如果你有一个10^100的数字，则需要小于10^50的所有质数，这仍然是一个巨大的数量。

- corsiKa

---

判断数字是否为质数（素数）可能比分解它们要简单一些。有确定性的算法可以检验数字的质性，它们的时间复杂度与数字的位数呈多项式关系，但是目前并没有已知的对于因式分解的这样的算法。基本上，你可以证明一个数字是合数而不必列举出其因子，也可以证明它是质数而不必逐个穷举所有的候选因子。 - Steve Jessop

这个问题不是关于因式分解的，而是关于检查一个数是否为质数。对于几千位的质数，可以有效地进行素性测试。例如，使用概率性的Miller-Rabin测试。 - CodesInChaos

Answer 2

您列出的数字：2 ^ 7 - 1, 2 ^ 31 - 1, 2 ^ 127 - 1被称为梅森数。已经有一个分布式计算项目来寻找它们，名为GIMPS。

因此，回答您的问题并不简单。目前已知的所有形式的质数都在这里列出：

http://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes

- Mysticial

---

我认为你不可能比检查是否在已知表中更快。 - celion

Answer 3

你对数字有上限吗？你提到要处理天数。 如果是这样，除非你处理的数字非常大，否则你当前的算法可以工作。

你还可以查看米勒-拉宾素性检验

- rohit89

---

"2^127-1"非常大（事实上是质数，但你不会在几天内使用提问者的代码证明它）。 - Steve Jessop

Answer 4

Java自带一种概率性素数测试的实现——请参见java.math.BigInteger.isProbablePrime()。我原以为这意味着C#语言也有类似的功能，但实际上没有找到。不过，在寻找相关功能时，我在网站http://www.codeproject.com/KB/cs/biginteger.aspx上找到了一些代码。

- mcdowella