java - 澄清 isProbablePrime 中的确定性因子

Question

我的问题涉及 BigInteger 的 isProbablePrime() 方法的“确定性”因素。 Java API 声明这是:

"a measure of the uncertainty that the caller is willing to tolerate"

这是不确定性百分比还是其他因素。我需要 2 个 512 位的质数。

Answer 1

来自Javadocs for BigInteger's isProbablePrime method :

certainty - a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2^certainty)

因此，您传递的 certainty 数字越高，您就越确定，即 100 表示它是素数的概率为 1 - (1/2)¹⁰⁰，非常接近 1。

Java 通过执行 Miller-Rabin 素数测试来实现这一点，其数量基于确定性(和 Lucas-Lehmer 测试)。