Почему Java BigInteger говорит «вероятно, простое», а не «безусловно простое»?

Question

JavaDoc от BigInteger заставляет меня чувствовать себя очень неуверенно, например, следующий конструктор говорит:

BigInteger(int bitLength, int certainty, Random rnd)

Создает случайно сгенерированный положительный BigInteger, который, вероятно, простое число с указанным значением bitLength.

Почему только возможно? Почему нет конечно? Могу ли я все еще верить, что результатом будет простое число?

Answer 1

Поскольку вероятностный алгоритм работает намного быстрее, чем проверка того, что число определенно простое.

Answer 2

Из документов для BigInteger(int bitLength, int certainty, Random rnd):

certainty: мера неопределенности того, что вызывающий абонент готов терпеть. Вероятность того, что новый BigInteger представляет простое число будет превышать (1 - ½ ^{уверенность} ). Время выполнения этот конструктор пропорционален значению этого параметра.

Итак, конструктор позволяет вам указать, что он будет простым, поэтому в документах написано «вероятно»