澄清isProbablePrime中的確定性因子

Question

我的問題涉及BigInteger的isProbablePrime()方法的「確定性」因子。 Java的API指出，這就是：

「的不確定性的度量，來電者是願意忍受」

這是一個不確定性的百分比或其他一些因素。我需要512位的素數。

Answer 1

從Javadocs for BigInteger's isProbablePrime method：

確定性 - 不確定性的措施，調用者願意忍受：如果調用返回true即此BigInteger黃金超過的概率（1 - 1/2 ^確定性）

因此，較高你通過certainty數量越多，你一定可以的，即100意味着它主要以概率1 - （1/2），這非常接近1.

Java通過執行Miller-Rabin素數測試來完成此操作，其數量基於certainty（和Lucas-Lehmer測試）。