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

Question

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

1. 是否有任何特定的库可以执行此操作？

2. 还有其他(更好的)方法吗？

Answer 1

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

无论如何，这不会永远持续下去的原因是，根据素数定理，随机选择的 n 位数字成为素数的概率与 1/n 成正比，因此平均而言，您只需要尝试O(n) 个不同的随机 n 位数字，然后您才能找到一个素数。