java - 如何在 java 中生成 160 位素数？

Question

我想在 java 中生成一个 160 位素数。我知道我必须遍历所有 160 位数字，对于任何数字n，我必须检查它们是否可以被任何小于的素数sqroot(n)或任何素数测试（如Miller-Rabin test. 我的问题是：

1. 是否有任何特定的库可以做到这一点？

2. 还有其他（更好的）方法可以做到这一点吗？

Answer 1

BigInteger.probablePrime(160, new Random())生成一个BigInteger几乎可以肯定是素数的 - 它不是素数的概率小于你被闪电击中的概率。一般来说，BigInteger已经内置了经过大量测试和优化的素数测试操作。

对于它的价值，这不会永远持续下去的原因是，根据素数定理，随机选择的 n 位数字的概率与成为素数的 1/n 成正比，所以平均而言你只需要尝试 O(n ) 不同的随机 n 位数字，然后才能找到素数。