в исходники не смотрел, но certainty — это наверняка число раундов в тесте Миллера-Рабина. Каждый раунд работает за , вероятность ошибки падает по эскпоненте.

Если нужна абсолютная точность, то можно написать тест Миллера по нужным основаниям (см. вики).

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

Допустим, задача имеет 100 тестов, и Вы хотите получить AC с вероятностью 0.95. Значит, вероятность ответить правильно на тест должна быть . Решим неравенство , получим certainty ≥ 11 (округлил до целого). Как-то так.