java - 用Java生成完全素数

Question

我知道函数 BigInteger.probablePrime(int bitLength, Random rnd) 可能输出任何位长度的素数。我想要一个 Java 中的 REAL 素数。是否有任何 FOSS 库可以以可接受的性能做到这一点？提前致谢！

编辑：

我正在查看 1024 和 2048 位素数。

Answer 1

• 使用可能的素数生成候选
• 使用快速确定性测试（例如AKS 素数测试）来检查候选人是否确实是素数。

---

编辑：或者，如果您不相信 isProbablePrime 的确定性足够大，请使用 BigInteger 构造函数BigInteger(int bitLength, int certainty, Random rnd)来调整确定性阈值：

确定性 - 衡量调用者愿意容忍的不确定性。新的 BigInteger 表示素数的概率将超过（1 - 1/2^确定性）。此构造函数的执行时间与此参数的值成正比。

用于加密目的的概率测试可以保证限制误报的概率——这并不像存在一些会偷偷摸摸的陷阱数字，这只是你希望概率有多低的问题。如果您不相信 Java BigInteger 类可以使用这些（如果他们记录了使用的测试会很好），请使用Rabin-Miller测试。

Answer 2

有一些方法可以生成具有可接受性能的非常大的素数，但对于大多数目的来说，除了进入吉尼斯世界纪录之外，密度不够。

像这样看：返回的数字probablePrime()不是素数的可能性低于您和您认识的每个人被照明击中的可能性。两次。单日。

只是别担心。

Answer 3

您还可以使用构造函数BigInteger来生成一个真正的素数：

BigInteger(int bitLength, int certainty, Random rnd)

执行时间与确定性成正比，但在我的 Core i7 上这不是问题。

Answer 4

制作一个方法并包装它。

BigInteger definitePrime(int bits, Random rnd) {
    BigInteger prime = new BigInteger("4");
    while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
    return prime;
}

Answer 5

Random rnd = new SecureRandom();
System.out.println(BigInteger.probablePrime(bitLength, rnd));

BigInteger方法返回的复合概率probablePrime()不超过 2^-100。