Я знаю, что тест Миллера-Рабина на простоту будет требовать простоты для составного числа с в большинстве а $\фракция{1}{4}$ вероятность для некоторого произвольного нечетного составного $n$ и случайный свидетель $а$ выбираются равномерно в диапазоне $[2,n-1)$. Что это действительный средняя вероятность того, что тест ложно утверждает, что число простое? Как меняется шанс в зависимости от размера $n$ Продолжается? Как изменится шанс, если $n$ не делится ни на какие малые простые числа до, скажем, 2000?
Я спрашиваю, потому что Эта бумага описывает вероятность того, что композит выдержит определенное количество циклов испытаний. Вероятность $p_{k,t}$ с $к$ размер проверяемого числа в битах и $t$ количество раундов, которые нужно запустить. Бумага доказывает, что $\forall k \ge 2:p_{k,1} \le k^2 4^{2-\sqrt{k}}$, но это неравенство является лишь верхней оценкой, и существует отдельное доказательство, показывающее гораздо более сильную оценку $p_{600,1} \le 2^{-75}$. Я хотел бы найти функцию с сильной верхней границей для $p_{k,t,n}$ с $n$ будучи пробным делением против всех простых чисел, меньших, чем $n$, но я недостаточно хорошо понимаю математику этой статьи, чтобы придумать это.
В таблице 2 в статье приведены некоторые примеры нижних границ для $-\lg{p_{k,t}}$:
\begin{массив}{c|ccccccccc}
к/т&1&2&3&4&5&6&7&8&9&10\ \hline
100&5&14&20&25&29&33&36&39&41&44\
150&8&20&28&34&39&43&47&51&54&57\
200&11&25&34&41&47&52&57&61&65&69\
250&14&29&39&47&54&60&65&70&75&79\
300&19&33&44&53&60&67&73&78&83&88\
350&28&38&48&58&66&73&80&86&91&97\
400&37&46&55&63&72&80&87&93&99&105\
450&46&54&62&70&78&85&93&100&106&112\
500&56&63&70&78&85&92&99&106&113&119\
550&65&72&79&86&93&100&107&113&119&126\
600, 75, 82, 88, 95, 102, 108, 115, 121, 127, 133
\конец{массив}
Генерация ключей OpenSSL, по-видимому, предполагает, что это не так, поскольку она увеличивает количество раундов для больших простых чисел, создавая иллюзию того, что частота ложных срабатываний каким-то образом влияет на безопасность сгенерированного простого числа. Обратите внимание, что этот код используется в основном поколение рутина, поэтому гарантируется, что простые числа-кандидаты будут равномерно распределены и не подвержены ложноположительному результату в наихудшем случае.
От крипто/bn/bn_prime.c:87:
/*
* Используйте минимум 64 патрона Миллера-Рабина, что должно дать ложный результат.
* положительная скорость 2^-128. Если размер простого числа больше 2048
* пользователь, вероятно, хочет более высокий уровень безопасности, чем 128, поэтому переключитесь
* до 128 раундов, что дает ложноположительный результат 2^-256.
* Возвращает количество раундов.
*/
статический интервал bn_mr_min_checks (целые биты)
{
если (бит > 2048)
вернуть 128;
вернуть 64;
}
