BigInteger.probablePrime() 与 java 中其他素性算法的区别

Question

我正在使用 Java 实现 RSA 加密程序。现在我正在使用 BigInteger.probablePrime(1024, rnd) 来获取素数。这里 rnd 是由 Random rnd = new Random() 生成的随机数。 我需要测试各种加密速度。

我的问题是：

1. BigInteger.probablePrime(1024, rnd) 使用什么算法？

2. 上述算法与其他算法（如 Rabin-Miller、Fermats、Lucas-Lehmer）有何区别？

谢谢。

Answer 1

BigInteger 的可能素数方法使用 Miller-Rabin 和 Lucas-Lehmer 算法来测试素数。

查看内部方法 BigInteger.primeToCertainty< /a>.

Answer 2

Java源代码已经可以下载了，大家可以自己看一下。
以下是 BigInteger.probablePrime(int, Random) 的代码：

public static BigInteger probablePrime(int bitLength, Random rnd) {

    if (bitLength < 2)
        throw new ArithmeticException("bitLength < 2");

    // The cutoff of 95 was chosen empirically for best performance

    return (bitLength < SMALL_PRIME_THRESHOLD ?
            smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
            largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
}

实际测试包含在 smallPrime() 和 largePrime() 方法中，直接在源代码中。