5

我将 GMP（带 MPIR）用于任意大小的数据类型。我也使用了它的素数测试函数，它使用了 Miller-Rabin 方法，但它并不准确。这就是我想要解决的问题。

通过使用蛮力和 sqrt 方法，我能够确认数字 18446744073709551253 是素数。

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

  • 它不应该使用太多的内存/存储空间，几兆字节是可以接受的。

  • 它应该比我使用的 sqrt 方法更快。

  • 它应该适用于大小至少为 64 位或更大的数字。

  • 最后，它应该是 100% 准确的，没有可能！

我有什么选择？

虽然我可以使用蛮力方法（对于 64 位数字），但出于兴趣，我想要更快、更大。此外，64 位数字检查太慢：总共 43 秒！

4

4 回答 4

6

对于非常大的数字，AKS 素数测试是一种确定性素数测试，运行时间为 O(log 7.5 n log log n)，其中 n 是感兴趣的数字。这比 O(√n) 算法要快得多。但是，该算法具有较大的常数因子，因此在您的数字变得相当大之前它是不实用的。

希望这可以帮助！

于 2012-12-11T22:07:04.193 回答
3

一般来说，100% 的确定性在物理计算机上是不可能的，因为某些组件在不可见的情况下发生故障并且最后给出的答案不正确的可能性很小但有限。鉴于这一事实，您可以运行足够多的概率 Miller-Rabin 测试，以证明数字复合的概率远小于硬件发生故障的概率。测试高达 1 in 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

这将测试该数字是否为素数，确定性为 2 ^ 256 中的 1。每个 MR 测试将确定性增加四倍。我已经看到了由此产生的素数，称为“工业强度素数”，对于所有实际目的来说都足够好，但对于理论上的数学确定性来说还不够。

于 2012-12-12T13:23:04.033 回答
1

证明的方法取决于您要证明的素数的类型（例如，梅森素数有证明素数的特殊方法仅适用于它们）和十进制数字的大小。如果您正在查看数百个数字，那么只有一种解决方案，尽管不够充分：AKS 算法。对于足够大的素数，它明显比其他素数证明算法快，但是当它变得有用时，它会花费很长时间，以至于它真的不值得麻烦。

大数的素性证明仍然是一个尚未充分解决的问题。如果是这样，EFF 奖项将全部颁发，密码学将出现一些问题，不是因为素数列表，而是因为用于找到它们的方法。

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

于 2012-12-16T07:22:46.537 回答
1

对于小n，试分工；那里的限制可能在 10^12 左右。对于稍大的n，有各种研究（参见 Gerhard Jaeschke 和 Zhou Zhang 的作品）计算各种 Miller-Rabin 基集合的最小伪素数；这将带你到大约 10^25。在那之后，事情变得艰难。

素数证明的“大炮”是 APRCL 方法（它可能被称为雅可比和或高斯和）和 ECPP 方法（基于椭圆曲线）。两者都很复杂，所以你会想找到一个实现，不要自己写。这些方法都可以处理几百位数的数字。

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

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

对于所有这些，您希望在尝试证明某个数字之前合理地确定它是素数。如果你的数不是素数，所有这些方法都会正确地确定这一点，但首先它们会浪费很多时间来试图证明一个合数是素数。

我的博客上有AKS和Pocklington的实现。

于 2012-12-12T14:01:31.347 回答