为什么 Java BigInteger 说“可能是素数”而不是“肯定是素数”？

Question

BigInteger的JavaDoc让我觉得很不安全，例如下面的构造函数说：

BigInteger(int bitLength, int certainty, Random rnd)

构造一个随机生成的正 BigInteger，它可能是质数，具有指定的 bitLength。

为什么只有大概？为什么不肯定？我还能相信结果是质数吗？

Answer 1

从文档中BigInteger(int bitLength, int certainty, Random rnd)：

certainty：衡量调用者愿意容忍的不确定性。新 BigInteger 表示质数的概率将超过 (1 - ½^确定性)。此构造函数的执行时间与此参数的值成正比。

所以构造函数让你指定它是素数的确定性，这就是为什么文档说“可能”

Answer 2

因为概率算法的运行速度比验证数字肯定是素数要快得多。