Блог пользователя naik

Как правильно подобрать параметр к функции isProbablePrime класса BigInteger ?
Автор naik, история, 8 лет назад, По-русски

Добрый день! Подскажите, пожалуйста, как подобрать точность для проверки числа на простоту к методу:

public boolean isProbablePrime(int certainty)

Например, чтобы функция работала быстро и точно для чисел до миллиарда.

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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

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

→ Ответить