最快的素性测试

Question

你能否建议一种在实践中可用的快速,确定性的方法,用于测试大数是否为素数？

另外,我想知道如何正确使用非确定性素性测试.例如,如果我使用这样的方法,如果输出为"no",我可以确定数字不是素数,但是当输出"可能"时,另一种情况呢？在这种情况下,我是否必须手动测试素数？

提前致谢.

Answer 1

我所知道的唯一确定性多项式时间算法是AKS素性测试(http://en.wikipedia.org/wiki/AKS_primality_test).然而,有很多非常好的随机素性测试很快并且具有极好的成功概率.他们通常通过查找数字是否具有指数级概率的复合来工作,因此他们要么报告该数字是复合的,要么要求您以非常好的信心说"可能".

Answer 2

"可能"实际上意味着1-ε,并且ε变得尽可能小.

例如,大多数应用程序具有一些小但非零的失败概率,这与概率测试无关

• 在加密应用程序中,攻击者幸运地猜测秘密,例如,概率为2 ^( - 100)

• 硬件故障(辐射引起)随机翻转你的计算机内存(可能是一个保存你的"确定性"素性测试的输出

• 错误(事实上,比其他类型的失败更可能)

因此,将ε按到这个数量级就足够了.

例如,OpenSSL,GnuPG仅使用非确定性素性测试.``'可能''你真的不想要没有确定性测试.但请检查可用的内容:如果您手头有任何库,并且它们的性能足够 - 请继续使用它们.