最快的素数测试算法

Question

我需要在非常大的数字(在很长的范围内)之间的间隔上测试素数,所以我需要一些快速算法来检查数字是否为素数.请提出您的想法.

Answer 1

一个好的方法是Miller-Rabin测试.然而,应该注意,这只是一个概率测试.

在广义黎曼假设的假设下,米勒 - 拉宾可以被认为是确定性的.由于GRH被广泛认为是真的,我可以设想你使用这个测试的场景,好像它被证明是确定性的,因为它是迄今为止最快的. (4认同)
@Mark:对于指定的输入范围,我们不需要假设GRH是真的,我们只需要一个较弱的假设,即MR的确定性版本在LONGLONG_MAX之下没有误报.这可能更容易证明,虽然我仍然不想通过详尽的测试来尝试这样做. (3认同)

Answer 2

Jim Sinclair已证实对七个碱基2,355,9375,28178,450775,9780504,1795265022进行了Miller-Rabin检验,以确定性地测试小于2 ^ 64的数是否为素数.看到 http://miller-rabin.appspot.com/.

Answer 3

我相信渐近最快的当前(非概率)素性测试是"Lenstra/Pomerance改进的AKS",其复杂性基本上是O(n ^ 6).

但是,long long(假设典型系统是64位整数)的范围并不是那么大.特别是,只有大约2亿个质数小于2 ^ 32,因此使用快速概率检验,然后使用预先计算的素数列表进行试验分割(或者只是查看素数列表中的数字,如果有的话)在这个范围内会非常快,并且可能是正确的方法.

特别是,在真实硬件上,您很快就会达到概率测试失败的可能性并不比确定性测试由于异常高能宇宙射线(或其他零星的硬件故障)导致寄存器值翻转而导致失败的可能性. (7认同)

Answer 4

我建议使用Miller-Rabin算法的GNU MP库.我已经用了几个月而且速度非常快.

具体来说,函数mpz_probab_prime_p执行此操作,您还可以使用另一个函数mpz_nextprime来查找大于数字的下一个素数.如果您愿意,我可以发布代码示例.

Answer 5

我提出了一个非常好的算法,比检查所有除数要快得多 - 这当然也让我破解了公钥加密.

坚持 - 我只需要关闭窗户,所有这些黑色直升机都在头顶........

对复合数进行因式分解(破解RSA所需)与仅测试一个数是否为素数(不一定需要找到任何特定因子)不同.事实上,实现RSA需要找到具有数百个数字的素数,这对于简单的"检查所有可能的除数"算法是不可行的. (4认同)

Answer 6

如果你想长期测试素数,那么Baillie PSW素性测试是一个不错的选择.该测试进行了一次强伪测试和一次Lucas测试,因此非常快.预计会有一些复合材料通过这个测试,但到目前为止还没有人知道,并且在10 ¹⁵以下肯定没有例外.该测试的变体例如在Mathematica中使用.