Модифицированная версия Миллера-Рабина для проверки детерминированной простоты?

В тесте Миллера-Рабина используется k. случайные целые числа для проверки на простоту.

Согласно CLRS, 3rd Edition, стр. 971:

Теорема 31.38.

Если n — нечетное составное число, то количество свидетелей составности n не меньше (n — 1)/2.

Тогда почему бы нам просто не запустить случайные тесты k раз, использовать разные ( n - 1 ) / 2 значения и проверить их на простоту? Поскольку все простые числа, кроме 2, нечетны, а число свидетелей не меньше (n - 1)/2, мы гарантированно найдем свидетеля, если он существует.


algorithm primes proof primality-test
person Existent    schedule 06.06.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Время выполнения увеличивается от poly(log(n)) до n*poly(log(n)), что ужасно для больших чисел, поскольку n экспоненциально больше, чем log(n).

person David Eisenstat    schedule 06.06.2016
comment
Но он по-прежнему использует k тесты. Действительно ли выбранное k меньше половины значения числа? Какое значение используется тогда? - person Existent; 06.06.2016
comment
@ABHI k очень маленький. Оригинальный тест Миллера, который требует обобщенной гипотезы Римана, устанавливает k = O (log ^ 2 n). - person David Eisenstat; 06.06.2016