0

我正在寻找一种算法，它可以证明任何大数的素数。大数是指其中至少有 100,000,000 个十进制数字的数字，不能用梅森素数等简单的公式表示。

以下是我的要求：

1-它必须完全正确

2-它必须可以在基本的家用计算机上运行

3- 它必须在几周或几个月内完成它的课程。

我的内存限制是 8 GB 的内存（我可以设置我的选项来决定有多少缓存可用），在具有 1 TB 硬盘驱动器的专用机器上。在几个月的时间里，我将一次次考虑排名第一。

Edit1：我很清楚这是一个很难竞争的竞技场，如果使用当前的方法几乎不可能的话。我没有使用当前的方法，我需要一种方法来证明我的方法对于非常大的数字是正确的。

Edit2：我需要一种非概率方法的部分原因是因为这将是对 EFF 奖项的尝试，并且在那里成功获得第二个 EFF 奖项。如果我的方法是正确的（这是一个按喇叭的 IF），我应该可以用我的笔记本电脑完成所有这些工作。

4

1 回答 1

1

据我了解，您正在寻找一种算法：

  • 确定性的
  • 相当快
  • 具有相当合理的内存占用

我不确定最后一部分，因为我从未尝试过实现它（还），但我知道素数问题已经解决了一般数字。换言之，无论形式如何，您都可以 100% 确定地确定一个数是否为素数。您应该查看AKS 素性测试，这是解决此问题的第一个已知算法。

就像你说的，运行可能需要一段时间，但最终会以一定的答案结束。优化版本的复杂度为 O((log n)^7.5（log n 与 n 的位数成正比）。

但是，由于此运行时非常大，并且您想要测试大量数字，因此您应该首先考虑使用更快的非确定性算法过滤这些数字。换句话说，我会尝试运行Miller-Rabin 测试对于一些数字（a=2,3,5,7,... - 前十个素数应该足够了，但即使你真的想要更高的精度，你可能不应该超过 50 个素数）。如果我没记错的话，在 k Miller-Rabin 测试之后被测试的数字是假素数的概率小于 1/4^k。换句话说，您可以运行少量测试（更不用说这些测试非常快），并且对数字是否为质数非常有信心（如果这些测试中的任何一个失败，则该数字绝对不是质数）。在所有 MR 测试通过后，对测试号码运行 AKS 算法以确保（正如您在 MR 维基百科页面上看到的那样，即使进行了几次测试，最小的误报也会以非常快的速度增加）。

于 2012-11-22T05:49:58.117 回答