100%确定的快速素数检测？

Question

我正在使用GMP（与MPIR一起）处理任意大小的数据类型。我还使用它的素性测试功能，它使用的是Miller-Rabin方法，但不准确。这就是我想要解决的问题。

我能够证实通过暴力方法和sqrt方法，数字18446744073709551253是质数。

有没有办法以100%的准确率检查大数字是否是质数？

以下是我的要求：

- 它不应该占用太多的内存/存储空间，几兆字节是可以接受的。 - 它应该比我使用的sqrt方法更快。 - 它应该适用于至少64位或更大的数字。 - 最后，它应该是100％准确的，无论如何！

我的选择是什么？

尽管我可以接受暴力方法（对于64位数字），但出于兴趣，我想要更快速且可处理更大的数字。而且，64位数字的检查速度太慢了：总计43秒！

- Rookie

---

对于小于2^64的数字，Baillie Pomerance Selfridge Wagstaff测试是可靠的。超过这个范围，需要使用APRCL或椭圆曲线素性证明。 - Daniel Fischer

@Grizzly，我需要它放在哪里？当然是在我的脑海中 :) 如果我在程序中制作一个按钮来告诉数字是否为质数，听到“也许它是质数，我不知道，问别人吧！”是很烦人的！:p - Rookie

@Rookie：“也许”可能不是正确的术语。使用Miller-Rabin算法，您可以轻松地使错误阳性的概率小于您的计算机错误计算的概率（毕竟内存中的位错误并非不可能）或随机着火的概率。由于我假设您没有考虑这些情况，所以“100％确定”是一个有点模糊的术语。 - Grizzly

@Grizzly，让我烦恼的是我知道有错误的可能性，而且通常当这种情况出现时，凭借我的运气，我总是会输入唯一可能掉进错误陷阱的值！（我不是在开玩笑！）此外，我希望这些事情能够精确无误。正如你所说的“也许”，如果不能100％确定是质数，那么“质数”这个术语在这里就不是正确的术语。 - Rookie

@新手：那么你对于随机位错误、自发硬件故障等情况怎么处理？我的观点是，例如1/2^512这样的概率不仅仅是不太可能发生。由于a）计算更有可能因为硬件缺陷而失败，而不是因为假阳性；b）即使你让你的计算机（甚至是世界上所有现有的计算机）从现在开始不断测试素数，你也不会在你的一生中（或者是这个宇宙估计剩余的寿命）看到一个假阳性。 - Grizzly

Answer 1

对于非常大的数，AKS素性检验是一种确定性素性检验，其运行时间为O(log^7.5n log log n)，其中n是所关心的数字。 这比O(√n)算法快指数级。 但是，该算法具有很大的常数因子，因此在您的数字变得相当大之前并不实用。

希望这可以帮到您!

- templatetypedef

---

在谷歌上搜索“AKS GMP”可以找到一些有趣的讨论。 - brian beuning

那么，使用AKS算法，我的数字至少要有多大？ - Rookie

@Rookie- AKS算法总是有效的，但对于小数字可能比其他方法慢。老实说，我不知道它在64位整数上运行的速度有多快。 - templatetypedef

Answer 2

通常情况下，在物理计算机上无法100％确定，因为有可能某些组件已经发生难以察觉的故障，导致最终给出的答案不正确。 鉴于这个事实，您可以运行足够的概率性 Miller-Rabin 测试，使得该数字是合数的概率远小于硬件故障的概率。 很容易测试到 1/2^256 的确定性水平:

boolean isPrime(num)
  limit <- 256
  certainty <- 0
  while (certainty < limit)
    if (millerRabin returns notPrime)
      return false
      exit
    else
      certainty <- certainty + 2
    endif
  endwhile
  return true
end isPrime

这将检测该数字是否为质数，确信度高达1/2^256。每次M-R测试将增加四倍的确信度。结果为素数的称为“工业级素数”，足够实际应用，但不太符合理论数学的确信度要求。

- rossum

Answer 3

对于小的n，试除法是有效的；其限制大约在10^12左右。对于稍大的n，有各种研究（参见Gerhard Jaeschke和Zhou Zhang的作品），可以计算出各种Miller-Rabin基数集合的最小伪素数；这将带您到大约10^25。之后，事情就变得困难了。

素性证明的“大杀器”是APRCL方法（也称为Jacobi和或Gaussian和）和ECPP方法（基于椭圆曲线）。两者都很复杂，因此您需要找到一个实现，而不是编写自己的代码。这些方法都可以处理几百位数字。

AKS方法已被证明是多项式时间，并且易于实现，但比例常数非常高，因此在实践中并不实用。

如果您可以分解n-1，甚至部分分解它，Pocklington方法可以确定n的素性。 Pocklington方法本身很快，但因子分解可能不快。

对于所有这些，您希望在尝试证明一个数字是质数之前相当确定它是质数。如果您的数字不是质数，所有这些方法都将正确地确定，但首先它们将浪费大量时间尝试证明一个合成数是质数。

我在我的博客上实现了AKS和Pocklington的链接1和链接2。

- user448810

Answer 4

证明质数的方法取决于您要证明的质数类型（例如，梅森质数有特殊的证明质数方法，只适用于它们）和十进制位数的大小。如果您正在查看数百个数字，则只有一种解决方案，尽管不足：AKS算法。对于足够大的质数，它可以被证明比其他质数证明算法更快，但到它变得有用的时候，需要的时间太长了，真的不值得麻烦。

大数的质数证明仍然是一个尚未得到充分解决的问题。如果解决了这个问题，EFF奖项将全部颁发，并且加密学将面临一些问题，不是因为质数列表，而是因为用于找到它们的方法。

我相信，在不久的将来，将出现一种新的证明质数算法，它不依赖于预先生成的质数列表，直到n的平方根，并且不使用暴力方法确保所有小于平方根的质数（以及许多非质数）都用作n的质数证人。这种新算法可能会依赖于比解析数论使用的数学概念简单得多的数学概念。质数中存在模式，这是确定的。识别这些模式是完全不同的问题。

- Adam