java - Java probablePrime 性能

Question

关于probablePrime的 Javadoc ：

返回一个可能是素数的正 BigInteger，具有指定的 bitLength。此方法返回的 BigInteger 是复合的概率不超过 2-100。

我的问题是，通过不保证质数，但几乎可以肯定，这可以获得多少性能？此外，这种性能差异真的值得在未来某个时间发生错误的微小机会吗？特别是如果加密的有效性取决于这个数字是素数。

Answer 1

其核心probablePrime()是一系列Miller-Rabin测试（执行的轮数取决于数字的位大小）与Lucas-Lehmer primality test相结合。这些的时间复杂度在很大程度上取决于BigInteger实现的其余部分。从维基百科接受“慢”估计将分别为 O(k log(n)^3) 和 O(log(n)^3)。

另一方面，AKS-primality test没有未经证实的猜想，可以在 Õ(log(n)^6) 中运行。

因此，假设您的数字足够大，概率测试可能比确定性测试快很多。对于任何足够大的密码学来说，渐近行为很可能是可观察到的。当然，唯一确定的方法是实施修改后的 AKS 并对结果进行计时。

（k是 Mille-Rabin 中的循环数）。

Answer 2

如果你有这个：

特别是如果加密的有效性取决于这个数字是素数

那么我认为你不应该使用这种约束probablePrime。因为你不能保证你的算法的正确性。

但是，如果获得非素数的概率如此之低以至于与例如SHA-1 碰撞概率相当，那么你可以接受它。（如果 git 对它没问题，那么你就是）

如果您使用给定范围内的素数池，那么您可以预先生成素数列表并将它们放入查找表中。这会给你O(1)时间复杂度。