关于 probablePrime 的 Javadoc :
Returns a positive BigInteger that is probably prime, with the specified bitLength. The probability that a BigInteger returned by this method is composite does not exceed 2-100.
我的问题是，通过不保证素数，但使其几乎确定，可以获得多少性能？另外，这种性能差异真的值得将来某个时候出现错误的微小机会吗？特别是当加密的有效性取决于该数字是否为质数时。
最佳答案
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 中的循环数)。
关于Java probablePrime 性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19321170/