performance - 检查 14 位数字是否为质数的最快算法是什么？

Question

我需要最快的程序来对 14 位(或更大)数字进行素性检查。我在多个网站上进行了搜索，但我不确定我找到的网站是否适用于像这样大的数字。

Answer 1

就质数测试而言，14 位数字不是很大。当数字有一些特殊的结构时，可能会有更快的专门测试(例如，如果它是梅森数)，但一般来说，对该范围内的数字进行最快的测试是

1. 开始尝试用一些小数除法。如果您计划进行多次检查，则值得列出 n最小素数，以便试验除法仅除以素数，对于单个测试，只需避免偶数测试除数(2 除外)和 3 的倍数(3 除外)就足够了。什么是“小”是要解释的，截断点在 100 到 10000 之间的选择似乎是合理的，许多(少数)除法仍然很快完成，并且他们找到了绝大多数合数。

2. 如果试验部门尚未确定该数为合数(或素数，如果它实际上小于截断值的平方)，您可以使用已知对以下问题具有决定性的快速概率素数测试之一你感兴趣的范围，通常的候选人是

   • Baillie/Pomerance/Selfridge/Wagstaff 检验，对基数 2 进行强费马检验，然后是正方形检验和(强)Lucas 检验。它没有低于 2⁶⁴ 的误报，因此对于 14-18 位数字是确定的。
   • 对一组已知对所考虑的范围具有决定性的碱基进行强费马测试。根据Chris Caldwell's prime pages , "如果 n < 341,550,071,728,321 是 2、3、5、7、11、13 和 17-SPRP，则 n 是素数"。

速度较慢且实现起来相当困难的是快速确定性通用素数测试、APR-CL、ECPP、AKS。他们应该已经在 14 位或更多位数的数字上击败了纯试验除法，但比偶然已知的范围正确概率测试要慢得多。

但是，根据您的用例，最好的方法也可能是筛选连续范围的数字(如果您想找到 10¹⁴-10^{9< 之间的素数/sup> 和 1014，例如，一个筛子比数亿个快速的单个素数测试要快得多)。}