<分区>
我正在寻找一种算法，可以证明任何 大数的素性。大数是指至少有 100,000,000 位十进制数字的数字，这些数字不能用梅森素数等简单公式表示。
这是我的要求:
1-必须完全正确
2- 它必须可以在基本的家用电脑上运行
3- 它必须在几周或几个月内完成类(class)。
我的内存限制是在配备 1tb 硬盘驱动器的专用机器上使用 8 GB 内存(我可以设置可用缓存量的选项)。在几个月的时间里，我将一次考虑一个数字。
Edit1:我很清楚这是一个很难竞争的领域，如果使用当前的方法，这几乎是不可能的。我没有使用当前的方法，我需要一种方法来证明我的方法适用于非常大的数字。
Edit2:我需要非概率方法的部分原因是因为这将是一次获得 EFF 奖项的尝试，并且在那里取得成功，获得第二次 EFF 奖项。如果我的方法是正确的(这是一个令人兴奋的 IF)，我应该能够用我的笔记本电脑完成所有这些工作。
最佳答案
据我了解，您正在寻找一种算法:
我不确定最后一部分，因为我(还)从未尝试实现它，但我知道素数问题已针对一般数字解决。换句话说，无论形式如何，您都可以 100% 确定一个数是否为素数。你应该看看 AKS primality test这是解决此问题的第一个已知算法。
就像你说的，它可能需要一段时间才能运行，但它最终会以某个答案结束。优化后的版本复杂度为O((log n)^7.5(log n与n的位数成正比)。
但是，由于此运行时非常大并且您想要测试大量数字，因此您应该考虑首先使用更快的非确定性算法来过滤这些数字。换句话说，我会尝试运行 Miller-Rabin test对于一些数字(a=2,3,5,7,... - 前十个素数应该足够了，但即使你真的想要更好的准确性，你也可能不应该超过 50 个素数)。如果我没记错的话，经过 k 次 Miller-Rabin 测试后，测试数为假素数的概率小于 1/4^k。换句话说，您可以运行少量测试(更不用说这些测试非常快)并且非常有信心数字是否为素数(如果这些测试中的任何一个失败，则该数字肯定不是素数)。在所有 MR 测试通过后，对测试的数字运行 AKS 算法以确保(正如您在 MR 维基百科页面上看到的那样，即使进行了几次测试后，最小的误报也会以非常快的速度增加)。
关于algorithm - 无特定形式的极大整数的素数证明算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13505515/