用Java生成精确的素数

Question

我知道函数 BigInteger.probablePrime(int bitLength, Random rnd) 可能输出任何位长度的素数。我想要一个 Java 中的实素数。是否有任何 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));

probablePrime() 返回 BigInteger 的概率是合数不超过2^-100。