Тест на простоту Миллера – Рабина

Тест на примитивность

Тест на простоту Миллера-Рабина или тест на простоту Рабина-Миллера — это вероятностный тест на простоту : алгоритм , который определяет, может ли данное число быть простым , аналогично тесту на простоту Ферма и тесту на простоту Соловея-Штрассена .

Это имеет историческое значение для поиска детерминированного критерия простоты с полиномиальным временем . Его вероятностный вариант до сих пор широко используется на практике как один из самых простых и быстрых известных тестов.

Гэри Л. Миллер открыл этот тест в 1976 году. Версия теста Миллера является детерминистической , но ее правильность основана на недоказанной расширенной гипотезе Римана . ^[1] Майкл О. Рабин модифицировал его, чтобы получить безусловный вероятностный алгоритм в 1980 году. ^{[2] [a]}

Математические концепции

Подобно тестам Ферма и Соловея-Штрассена, тест на простоту Миллера-Рабина проверяет, справедливо ли определенное свойство, которое, как известно, справедливо для простых значений, для проверяемого числа.

Сильные вероятные простые числа

Свойство следующее. Для заданного нечетного целого числа n > 2 запишем n − 1 как 2 ^s d , где s — положительное целое число, а d — нечетное положительное целое число. Давайте рассмотрим целое число  a , называемое основанием , которое взаимно просто с n . Тогда говорят , что n является сильным вероятным простым числом для основания a , если выполняется одно из этих отношений сравнения :

• ${\displaystyle a^{d}\equiv 1{\pmod {n}}}$;
• ${\displaystyle a^{2^{r}d}\equiv -1{\pmod {n}}}$ для некоторого 0 ≤ r < s .

Это упрощает сначала проверку, а затем последовательных значений r. Для каждого значения r значение выражения может быть рассчитано с использованием значения, полученного для предыдущего значения r путем возведения в квадрат по модулю n. ${\displaystyle a^{d}{\bmod {n}}=1}$ ${\displaystyle a^{2^{r}d}=n-1}$

Идея этого теста заключается в том, что когда n — нечетное простое число, оно проходит тест по двум причинам:

• по малой теореме Ферма ( только это свойство определяет более слабое понятие вероятного простого числа для основания a , на котором основан критерий Ферма); ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$
• единственные квадратные корни из 1 по модулю n - это 1 и -1.

Следовательно, в противоположность этому , если n не является сильным вероятным простым числом для основания a , то n определенно составное, и a называется свидетелем составности n .

Однако это свойство не является точной характеристикой простых чисел. Если n составное, оно, тем не менее, может быть сильным вероятным простым числом, лежащим в основе a , и в этом случае оно называется сильным псевдопростым числом , а a — сильным лжецом .

Выбор баз

К счастью, ни одно составное число не является сильным псевдопростым числом по всем основаниям одновременно (в отличие от теста на простоту Ферма, для которого существуют псевдопростые числа Ферма по всем основаниям: числа Кармайкла ). Однако простой способ найти свидетеля неизвестен. Наивным решением является перебор всех возможных базисов, что приводит к неэффективному детерминированному алгоритму. Тест Миллера является более эффективным его вариантом (см. раздел Тест Миллера ниже).

Другое решение — выбрать базу случайным образом. Это дает быстрый вероятностный тест . Когда n составное, большинство баз являются свидетелями, поэтому тест обнаружит n как составное с достаточно высокой вероятностью (см. раздел «Точность» ниже). Мы можем быстро снизить вероятность ложного срабатывания до сколь угодно малого уровня, объединив результаты стольких независимо выбранных баз, сколько необходимо для достижения указанной скорости. Это тест Миллера-Рабина. Количество баз, которые нужно попробовать, не зависит от n . Кажется, что попытка использовать множество оснований дает меньшую отдачу, потому что, если n является псевдопростым по отношению к какому-то основанию, то с большей вероятностью оно будет псевдопростым по отношению к другому основанию. ^{[4] : §8}

Обратите внимание, что a ^d ≡ 1 (mod n ) тривиально выполняется для a ≡ 1 (mod n ) , поскольку отношение сравнения совместимо с возведением в степень . И a ^d = a ^{2 0 d} ≡ −1 (mod n ) тривиально выполняется для a ≡ −1 (mod n ) , поскольку d нечетно по той же причине. Вот почему случайные a обычно выбираются в интервале 1 < a < n − 1 .

Для проверки произвольно большого n важен случайный выбор баз, поскольку мы не знаем распределения свидетелей и сильных лжецов среди чисел 2, 3, ..., n − 2 . ^[б]

Однако заранее выбранный набор из нескольких небольших оснований гарантирует идентификацию всех композитов вплоть до заранее рассчитанного максимума. Этот максимум, как правило, довольно велик по сравнению с базами. Это дает очень быстрые детерминированные тесты для достаточно малого n (см. раздел «Тестирование на небольших наборах оснований» ниже).

Доказательства

Вот доказательство того, что если n — простое число, то единственные квадратные корни из 1 по модулю n — это 1 и −1.

Доказательство

Конечно, 1 и −1, возведенные в квадрат по модулю n , всегда дают 1. Осталось показать, что не существует других квадратных корней из 1 по модулю n . Это частный случай, применяемый здесь с многочленом X ² − 1 над конечным полем Z / n Z , более общего факта, что многочлен над некоторым полем имеет не больше корней , чем его степень (эта теорема следует из существования евклидово деление многочленов ). Далее следует более элементарное доказательство. Предположим, что x — квадратный корень из 1 по модулю n . Затем:

${\displaystyle (x-1)(x+1)=x^{2}-1\equiv 0{\pmod {n}}.}$

Другими словами, n делит произведение ( x − 1)( x + 1) . По лемме Евклида , поскольку n является простым, оно делит один из множителей x − 1 или x + 1, подразумевая, что x конгруэнтен либо 1, либо −1 по модулю n .

Вот доказательство того, что если n — нечетное простое число, то оно является сильно вероятным простым числом для основания a .

Доказательство

Если n — нечетное простое число и мы пишем n − 1 = 2 ^s d , где s — целое положительное число, а d — нечетное целое положительное число, по малой теореме Ферма:

${\displaystyle a^{2^{s}d}\equiv 1{\pmod {n}}.}$

Каждый член последовательности представляет собой квадратный корень из предыдущего члена. Поскольку первый член равен 1, второй член представляет собой квадратный корень из 1 по модулю n . По предыдущей лемме оно конгруэнтно либо 1, либо −1 по модулю n . Если оно соответствует −1, все готово. В противном случае оно соответствует 1, и мы можем повторить рассуждения . В конце концов, либо один из членов конгруэнтен -1, либо все они конгруэнтны 1, и, в частности, последний член a ^d . ${\displaystyle a^{2^{s}d},a^{2^{s-1}d},\dots ,a^{2d},a^{d}}$

Пример

Предположим, мы хотим определить, является ли число простым. Мы пишем , чтобы у нас было . Мы случайным образом выбираем такое число , что . ${\displaystyle n=221}$ ${\displaystyle n-1{\text{ as }}2^{2}\times 55}$ ${\displaystyle s=2{\text{ and }}d=55}$ ${\displaystyle a}$ ${\displaystyle 2\leq a\leq n-2}$

Сказать : ${\displaystyle a=174}$

${\displaystyle {\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Since }}47\neq 1{\text{ and }}47\neq n-1{\text{, we continue.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}}$

Поскольку либо 221 — простое число, либо 174 — сильная ложь для 221. Мы пробуем еще одно случайное число , на этот раз выбирая : ${\displaystyle 220\equiv -1{\text{ mod }}n}$ ${\displaystyle a}$ ${\displaystyle a=137}$

${\displaystyle {\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &137^{{2^{0}}55}{\text{ mod }}221\equiv 137^{55}\equiv 188{\text{. Since }}188\neq 1{\text{ and }}188\neq n-1{\text{, we continue.}}\\&137^{{2^{1}}55}{\text{ mod }}221\equiv 137^{110}\equiv 205\neq n-1\end{aligned}}}$

Следовательно, 137 является свидетелем составности 221, а 174 на самом деле был ярым лжецом. Обратите внимание, что это ничего не говорит нам о факторах 221 (то есть 13 и 17). Однако пример с 341 в следующем разделе показывает, как эти вычисления иногда могут дать коэффициент n .

Практическое руководство по выбору значения a см. в разделе « Тестирование на небольших наборах оснований» .

Тест Миллера-Рабина

Алгоритм можно записать в псевдокоде следующим образом. Параметр k определяет точность теста. Чем больше количество раундов, тем точнее результат. ^[6]

Входные данные №1 : n > 2, нечетное целое число, которое необходимо проверить на простоту. Входные данные №2 : k , количество раундов тестирования. Выходные данные : « составное », если n оказывается составным, « вероятно, простое », в противном случае.

пусть  s > 0 и d нечетный > 0 такие, что n − 1 = 2 s d  # путем вынесения степеней 2 из n − 1 повторений  k  раз : a ← random(2, n − 2) # n всегда является вероятным простым числом по основанию 1 и n - 1 x ← a d mod n  повторить  s  раз : y ← x 2 mod n,  если  y = 1 и x ≠ 1 и x ≠ n - 1 , то  # нетривиальный квадратный корень из 1 по модулю n  возвращает « составной » x ← y,  если  y ≠ 1 , то  вернуть « составной », вернуть « вероятно, простой »

Сложность

При использовании повторного возведения в квадрат время работы этого алгоритма равно O ( k log ³ n ) , где n — количество проверенных на простоту, а k — количество выполненных раундов; таким образом, это эффективный алгоритм с полиномиальным временем. Умножение на основе БПФ ( алгоритм Харви-Хувена ) может уменьшить время работы до O( k log ² n log log n ) = Õ ( k log ² n ) .

Точность

Ошибка, допущенная при проверке на простоту, измеряется вероятностью того, что составное число будет объявлено вероятно простым. Чем больше оснований опробовано , тем выше точность теста. Можно показать, что если n составное, то не более1/4оснований a являются сильными лжецами для n . ^{[2] [7]} Как следствие, если n является составным, то выполнение k итераций теста Миллера-Рабина объявит n вероятно простым с вероятностью не более 4 ^{− k} .

Это улучшение по сравнению с тестом Соловея-Штрассена , чья граница ошибки в худшем случае равна 2 ^{- k} . Более того, критерий Миллера-Рабина строго сильнее критерия Соловея-Штрассена в том смысле, что для каждого составного n множество сильных лжецов для n является подмножеством множества лжецов Эйлера для n , а для многих n подмножество правильное.

Кроме того, для больших значений n вероятность того, что составное число будет объявлено простым, часто значительно меньше, чем 4 ^{- k} . Например, для большинства чисел n эта вероятность ограничена 8 ^{− k} ; доля чисел n , которые делают недействительной эту верхнюю границу, исчезает, когда мы рассматриваем большие значения n . ^[8] Следовательно, средний случай имеет гораздо лучшую точность, чем 4 ^{− k} , и этот факт можно использовать для генерации вероятных простых чисел (см. ниже). Однако не следует полагаться на такие улучшенные границы ошибок для проверки простых чисел, распределение вероятностей которых не контролируется, поскольку криптографический злоумышленник может послать тщательно выбранное псевдопростое число, чтобы обойти тест на простоту. ^[c] В таких контекстах можно полагаться только на границу ошибки для наихудшего случая , равную 4 ^{− k .}

Вышеупомянутая мера ошибки представляет собой вероятность того, что составное число будет объявлено как сильно вероятное простое число после k раундов тестирования; Говоря математическими словами, это условная вероятность , где P — это событие , когда проверяемое число является простым, а MR _k — это событие, когда оно проходит тест Миллера-Рабина с k раундами. Вместо этого нас часто интересует обратная условная вероятность : вероятность того, что число, объявленное как сильное вероятное простое число, на самом деле является составным. Эти две вероятности связаны законом Байеса : ${\displaystyle \Pr(M\!R_{k}\mid \lnot P)}$ ${\displaystyle \Pr(\lnot P\mid M\!R_{k})}$

${\displaystyle {\begin{aligned}\Pr(\lnot P\mid M\!R_{k})&={\frac {\Pr(\lnot P\land M\!R_{k})}{\Pr(\lnot P\land M\!R_{k})+\Pr(P\land M\!R_{k})}}\\&={\frac {1}{1+{\frac {\Pr(M\!R_{k}\mid P)}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{\Pr(\lnot P)}}}}\\&={\frac {1}{1+{\frac {1}{\Pr(M\!R_{k}\mid \lnot P)}}{\frac {\Pr(P)}{1-\Pr(P)}}}}\end{aligned}}}$

В последнем уравнении мы упростили выражение, используя тот факт, что все простые числа правильно указываются как сильно вероятные простые числа (тест не имеет ложноотрицательных результатов ). Опуская левую часть знаменателя , мы получаем простую верхнюю оценку:

${\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)}$

Следовательно, эта условная вероятность связана не только с обсуждавшейся выше мерой ошибки, которая ограничена 4 ^{- k}  , но также с распределением вероятностей входного числа. В общем случае, как было сказано ранее, это распределение контролируется криптографическим противником, поэтому неизвестным, поэтому мы не можем сделать много выводов о . Однако в случае, когда мы используем тест Миллера-Рабина для генерации простых чисел (см. ниже), распределение выбирается самим генератором, поэтому мы можем использовать этот результат. ${\displaystyle \Pr(\lnot P\mid M\!R_{k})}$

Детерминированные варианты

тест Миллера

Алгоритм Миллера-Рабина можно сделать детерминированным, перепробовав все возможные значения ниже определенного предела. Если принять n в качестве предела, это будет означать O( n ) попыток, следовательно, время работы будет экспоненциальным по отношению к размеру log n входных данных. Чтобы сократить время выполнения, задача состоит в том, чтобы максимально снизить предел, сохранив при этом надежность теста.

Если проверяемое число n является составным, сильные лжецы, взаимно простые с n , содержатся в собственной подгруппе группы ( Z / n Z )*, а это означает, что если мы проверяем все a из набора, порождающего ( Z / n Z )*, один из них должен лежать вне указанной подгруппы, следовательно, должен быть свидетелем составности n . Допуская истинность обобщенной гипотезы Римана (GRH), известно, что группа порождается своими элементами меньшими, чем O(( ln n ) ² ) , что было отмечено еще Миллером. ^[1] Константа, используемая в обозначении Big O, была уменьшена до 2 Эриком Бахом . ^[10] Это приводит к следующему алгоритму проверки простоты, известному как тест Миллера , который является детерминированным, предполагая GRH:

Входные данные : n > 2, нечетное целое число, которое необходимо проверить на простоту. Выходные данные : « составное », если n составное, в противном случае « простое ».

пусть  s > 0 и d нечетное > 0 так, что n − 1 = 2 s d  # путем вынесения степеней 2 из n − 1 для всех  a  в диапазоне [2, min( n − 2, ⌊2(ln n ) 2 ⌋)]: x ← a d mod n  повторить  s  раз : y ← x 2 mod n,  если  y = 1 и x ≠ 1 и x ≠ n - 1 , то  # нетривиальный квадратный корень из 1 по модулю n  вернуть « составной » x ← y,  если  y ≠ 1 , то  вернуть « составной » вернуть « простой »

Вся мощь обобщенной гипотезы Римана не нужна для обеспечения корректности теста: поскольку мы имеем дело с подгруппами четного индекса , достаточно предположить справедливость GRH для квадратичных характеров Дирихле . ^[7]

Время работы алгоритма в обозначениях soft-O равно Õ((log n ) ⁴ ) (с использованием умножения на основе БПФ).

Тест Миллера на практике не используется. В большинстве случаев правильное использование вероятностного теста Миллера-Рабина или теста простоты Бэйли-ПСВ дает достаточную уверенность при работе намного быстрее. На практике он также медленнее, чем обычно используемые методы доказательства, такие как APR-CL и ECPP , которые дают результаты, не основанные на недоказанных предположениях. Для теоретических целей, требующих детерминированного алгоритма с полиномиальным временем, он был заменен тестом простоты AKS , который также не опирается на недоказанные предположения.

Тестирование на небольших наборах баз

Когда число n , которое нужно проверить, невелико, перебирать все a < 2(ln n ) ² нет необходимости, поскольку известно, что достаточно гораздо меньшего набора потенциальных свидетелей. Например, Померанс, Селфридж, Вагстафф ^[4] и Йешке ^[11] подтвердили, что

• если n < 2,047, достаточно проверить a = 2;
• если n < 1 373 653, достаточно проверить a = 2 и 3;
• если n < 9 080 191, достаточно проверить a = 31 и 73;
• если n < 25 326 001, достаточно проверить a = 2, 3 и 5;
• если n < 3 215 031 751, достаточно проверить a = 2, 3, 5 и 7;
• если n < 4 759 123 141, достаточно проверить a = 2, 7 и 61;
• если n < 1 122 004 669 633, достаточно проверить a = 2, 13, 23 и 1662803;
• если n < 2 152 302 898 747, достаточно проверить a = 2, 3, 5, 7 и 11;
• если n < 3 474 749 660 383, достаточно проверить a = 2, 3, 5, 7, 11 и 13;
• если n < 341 550 071 728 321, достаточно проверить a = 2, 3, 5, 7, 11, 13 и 17.

Используя работу Фейтсмы и Голуэя по перечислению всех псевдопростых чисел по основанию 2 в 2010 году, это было расширено (см. OEIS : A014233 ), причем первый результат позже был показан с использованием различных методов у Цзяна и Дэна: ^[12]

• если n < 3 825 123 056 546 413 051, достаточно проверить a = 2, 3, 5, 7, 11, 13, 17, 19 и 23.
• если n < 18 446 744 073 709 551 616 = 2 ⁶⁴ , достаточно проверить a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и 37.

Соренсон и Вебстер ^[13] проверяют вышеизложенное и рассчитывают точные результаты для результатов, превышающих 64-битные:

• если n < 318 665 857 834 031 151 167 461, достаточно проверить a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и 37.
• если n < 3 317 044 064 679 887 385 961 981, достаточно проверить a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 и 41.

Существуют и другие критерии такого рода, часто более эффективные (требуется меньше оснований), чем показанные выше. ^{[14] [15] [16] [17]} Они дают очень быстрые детерминированные тесты на простоту для чисел в соответствующем диапазоне без каких-либо предположений.

Существует небольшой список потенциальных свидетелей для каждого возможного размера входных данных (не более b значений для b -битных чисел). Однако для всех составных чисел не существует конечного набора оснований. Алфорд, Гранвилл и Померанс показали, что существует бесконечно много составных чисел n , наименьший свидетель составности которых равен по крайней мере (ln n ) ^{1/(3ln ln ln n )} . ^[18] Они также эвристически утверждают, что наименьшее число w такое, что каждое составное число ниже n имеет свидетель составности меньше, чем w , должно иметь порядок Θ (log n log log n ).

Варианты поиска факторов

Включив вычисления наибольшего общего делителя в приведенный выше алгоритм, мы иногда можем получить коэффициент n вместо того, чтобы просто определять, что n является составным. Это происходит, например, когда n является вероятным простым числом по основанию a , но не является сильным вероятным простым числом по основанию a . ^{[19] : 1402}

Если x — нетривиальный квадратный корень из 1 по модулю n ,

• поскольку x ² ≡ 1 (mod n ) , мы знаем, что n делит x ² - 1 = ( x - 1)( x + 1) ;
• поскольку x ≢ ±1 (mod n ) , мы знаем, что n не делит ни x − 1 , ни x + 1 .

Отсюда мы делаем вывод, что A = НОД( x − 1, n ) и B = НОД( x + 1, n ) являются нетривиальными (не обязательно простыми) факторами числа n (фактически, поскольку n нечетно, эти факторы взаимно просты и п = АВ ). Следовательно, если целью является факторизация, эти вычисления НОД можно включить в алгоритм с небольшими дополнительными вычислительными затратами. Это приводит к следующему псевдокоду, где добавленный или измененный код выделен:

Входные данные №1 : n > 2, нечетное целое число, которое необходимо проверить на простоту. Входные данные №2 : k , количество раундов тестирования, которое необходимо выполнить . Выходные данные : (« кратное », m ), если найден нетривиальный коэффициент m от n , « составной », если в противном случае n оказывается составным, « вероятно, простое » иначе

пусть  s > 0 и d нечетный > 0 такие, что n − 1 = 2 s d # путем вынесения степеней 2 из n − 1 повторений  k  раз : a ← random(2, n − 2) # n всегда является вероятным простым числом по основанию 1 и n - 1  x ← a d mod n  повторить  s  раз : y ← x 2 mod n,  если  y = 1 и x ≠ 1 и x ≠ n - 1 , то  # нетривиальный квадратный корень из 1 по модулю n  возвращается (« кратное of », НОД( x − 1, n ))  x ← y,  если  y ≠ 1 , то  вернуть « составной » вернуть « вероятно простое »

Это не алгоритм вероятностной факторизации , поскольку он способен находить факторы только для чисел n , которые являются псевдопростыми по основанию a (другими словами, для чисел n таких, что a ^{n −1} ≡ 1 mod n ). Для других чисел алгоритм возвращает только « составное » без дополнительной информации.

Например, рассмотрим n = 341 и a = 2. Имеем n − 1 = 85 × 4 . Тогда 2 ⁸⁵ mod 341 = 32 и 32 ² mod 341 = 1 . Это говорит нам о том, что n является псевдопростым основанием 2, но не сильным псевдопростым основанием 2. Вычисляя НОД на этом этапе, мы находим коэффициент 341: НОД(32 - 1, 341) = 31 . Действительно, 341 = 11×31 .

Чтобы чаще находить факторы, те же идеи можно применить к квадратным корням из −1 (или любого другого числа). Эту стратегию можно реализовать, используя знания из предыдущих раундов теста Миллера-Рабина. В этих раундах мы могли бы определить квадратный корень по модулю n из −1, скажем, R . Затем, когда x ² mod n = n − 1 , мы можем сравнить значение x со значением R : если x не является ни R , ни n − R , то НОД( x − R , n ) и НОД( x + R , n ) являются нетривиальными факторами n . ^[14]

Генерация вероятных простых чисел

Тест Миллера-Рабина можно использовать для генерации сильных вероятных простых чисел, просто рисуя случайным образом целые числа, пока одно из них не пройдет тест. Этот алгоритм завершается почти наверняка (поскольку на каждой итерации есть шанс получить простое число). Псевдокод для генерации b - битных сильных вероятных простых чисел (с набором старших битов) выглядит следующим образом:

Входные данные №1 : b , количество бит результата. Входные данные №2 : k , количество раундов тестирования. Выходные данные : сильное вероятное простое число n.

пока правда: выберите случайное нечетное целое число n в диапазоне [2 b -1 , 2 b -1] , если тест Миллера-Рабина с входными данными n и k возвращает « вероятно простое число » , то  верните  n

Сложность

Конечно, время выполнения в худшем случае бесконечно, поскольку внешний цикл может никогда не завершиться, но это происходит с нулевой вероятностью. Согласно геометрическому распределению , ожидаемое количество розыгрышей равно (повторное использование обозначений, использованных ранее). ${\displaystyle {\tfrac {1}{\Pr(M\!R_{k})}}}$

Поскольку любое простое число проходит тест, вероятность быть простым дает грубую нижнюю границу вероятности прохождения теста. Если мы нарисуем нечетные целые числа равномерно в диапазоне [2 ^{b −1} , 2 ^b −1], то получим:

${\displaystyle \Pr(M\!R_{k})>\Pr(P)={\frac {\pi \left(2^{b}\right)-\pi \left(2^{b-1}\right)}{2^{b-2}}}}$

где π — функция подсчета простых чисел . Используя асимптотическое разложение π (расширение теоремы о простых числах ), мы можем аппроксимировать эту вероятность, когда b возрастает до бесконечности. Мы нашли:

${\displaystyle \Pr(P)={\tfrac {2}{\ln 2}}b^{-1}+{\mathcal {O}}\left(b^{-3}\right)}$

${\displaystyle {\tfrac {1}{\Pr(P)}}={\tfrac {\ln 2}{2}}b+{\mathcal {O}}\left(b^{-1}\right)}$

Следовательно, мы можем ожидать, что генератор выполнит не больше тестов Миллера-Рабина, чем число, пропорциональное b . Принимая во внимание сложность каждого теста Миллера-Рабина в наихудшем случае (см. ранее), ожидаемое время работы генератора с входами b и k затем ограничивается O( k b ⁴ ) (или Õ( k b ³ ) с использованием умножение на основе БПФ).

Точность

Мерой ошибки этого генератора является вероятность того, что он выдаст составное число.

Используя связь между условными вероятностями (показанными в предыдущем разделе) и асимптотическим поведением (показанным непосредственно перед этим), этой мере ошибки можно дать грубую верхнюю границу: ${\displaystyle \Pr(P)}$

${\displaystyle \Pr(\lnot P\mid M\!R_{k})<\Pr(M\!R_{k}\mid \lnot P)\left({\tfrac {1}{\Pr(P)}}-1\right)\leq 4^{-k}\left({\tfrac {\ln 2}{2}}b-1+{\mathcal {O}}\left(b^{-1}\right)\right).}$

Следовательно, для достаточно большого b эта мера ошибки меньше . Однако существуют гораздо лучшие границы. ${\displaystyle {\tfrac {\ln 2}{2}}4^{-k}b}$

Используя тот факт, что сам тест Миллера-Рабина часто имеет границу ошибки, намного меньшую, чем 4 ^{- k} (см. ранее), Дамгорд , Лэндрок и Померанс получили несколько границ ошибки для генератора с различными классами параметров b и k . ^[8] Эти границы погрешности позволяют разработчику выбрать разумное значение k для желаемой точности.

Одна из этих границ погрешности — 4 ^{− k} , которая справедлива для всех b ≥ 2 (авторы показали ее только для b ≥ 51, а Рональд Бурт-младший завершил доказательство с остальными значениями 2 ⩽ b ⩽ 50 ^[20] ). Опять же, эту простую оценку можно улучшить для больших значений b . Например, еще одна оценка, полученная теми же авторами:

${\displaystyle \left({\frac {1}{7}}b^{\frac {15}{4}}2^{-{\frac {b}{2}}}\right)4^{-k}}$

которое справедливо для всех b ≥ 21 и k ≥ b /4. Эта оценка меньше 4 ^{− k} , как только b ≥ 32.

Примечания

1. Часто ошибочно говорят, что тест Миллера-Рабина был открыт М. М. Артюховым еще в 1967 году; чтение статьи Артюхова ^[3] (особенно его теоремы E ) показывает, что он действительно открыл критерий Соловея–Штрассена.
2. Например, в 1995 году Арно дает 397-значное составное число, для которого все основания меньше 307 являются сильными лжецами; Функция Maple сообщила, что это число является простым isprime(), поскольку оно реализует тест Миллера-Рабина с конкретными основаниями 2, 3, 5, 7 и 11. ^[5]
3. Например, в 2018 году Альбрехт и др. смогли построить для многих криптографических библиотек, таких как OpenSSL и GNU GMP , составные числа, которые эти библиотеки объявили простыми, тем самым продемонстрировав, что они были реализованы без учета состязательного контекста. ^[9]

Рекомендации

1. Миллер, Гэри Л. (1976), «Гипотеза Римана и тесты на простоту», Журнал компьютерных и системных наук , 13 (3): 300–317, doi : 10.1145/800116.803773, S2CID  10690396
2. Рабин, Майкл О. (1980), «Вероятностный алгоритм проверки простоты», Журнал теории чисел , 12 (1): 128–138, doi : 10.1016/0022-314X(80)90084-0
3. Артюхов, М.М. (1966–1967), «Некоторые критерии простоты чисел, связанные с малой теоремой Ферма», Acta Arithmetica , 12 : 355–364, MR  0213289
4. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25 ⋅ 109» (PDF) . Математика вычислений . 35 (151): 1003–1026. дои : 10.1090/S0025-5718-1980-0572872-7 .
5. Ф. Арно (август 1995 г.). «Построение чисел Кармайкла, которые являются сильными псевдопростыми числами по нескольким основаниям». Журнал символических вычислений . 20 (2): 151–161. дои : 10.1006/jsco.1995.1042 .
6. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «31». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 968–971. ISBN 0-262-03384-4.
7. Schoof, Рене (2004), «Четыре алгоритма проверки простоты» (PDF) , Алгоритмическая теория чисел: решетки, числовые поля, кривые и криптография , Cambridge University Press, ISBN 978-0-521-80854-5
8. Дамгорд, И .; Лэндрок, П. и Померанс, К. (1993), «Оценки средней ошибки для сильного вероятностного простого теста» (PDF) , Mathematics of Computation , 61 (203): 177–194, Bibcode : 1993MaCom..61.. 177D, номер документа : 10.2307/2152945, JSTOR  2152945.
9. Мартин Р. Альбрехт; Джейк Массимо; Кеннет Г. Патерсон; Юрай Соморовский (15 октября 2018 г.). Простое и предубежденное: тестирование примитивности в состязательных условиях (PDF) . Конференция ACM SIGSAC по компьютерной и коммуникационной безопасности 2018. Торонто: Ассоциация вычислительной техники . стр. 281–298. дои : 10.1145/3243734.3243787.
10. Бах, Эрик (1990), «Явные границы для проверки простоты и связанных с ней проблем», Mathematics of Computation , 55 (191): 355–380, Bibcode : 1990MaCom..55..355B, doi : 10.2307/2008811 , JSTOR  2008811
11. Яшке, Герхард (1993), «О сильных псевдопростых числах по нескольким основаниям», Mathematics of Computation , 61 (204): 915–926, doi : 10.2307/2153262 , JSTOR  2153262
12. Цзян, Юпэн; Дэн, Инпу (2014). «Сильные псевдопростые числа по первым восьми простым основаниям». Математика вычислений . 83 (290): 2915–2924. дои : 10.1090/S0025-5718-2014-02830-5 . S2CID  33599405.
13. Соренсон, Джонатан; Вебстер, Джонатан (2015). «Сильные псевдопростые числа по двенадцати простым основаниям». Математика вычислений . 86 (304): 985–1003. arXiv : 1509.00864 . Бибкод : 2015arXiv150900864S. дои : 10.1090/mcom/3134. S2CID  6955806.
14. Колдуэлл, Крис. «Нахождение простых чисел и доказательство простоты - 2.3: Сильная вероятностная простота и практический тест». Главные страницы . Проверено 24 февраля 2019 г.
15. Чжан, Чжэньсян и Тан, Мин (2003), «Нахождение сильных псевдопростых чисел по нескольким основаниям. II», Mathematics of Computation , 72 (44): 2085–2097, Бибкод : 2003MaCom..72.2085Z, doi : 10.1090/S0025- 5718-03-01545-Х
16. Слоан, Нью-Джерси (ред.). «Последовательность A014233 (наименьшее нечетное число, для которого тест на простоту Миллера – Рабина по основаниям <= n-го простого числа не выявляет составность)». Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
17. Изиковский, Войцех. «Детерминистические варианты теста простоты Миллера – Рабина» . Проверено 24 февраля 2019 г.
18. Алфорд, WR ; Гранвилл, А. ; Померанс, К. (1994), «О сложности поиска надежных свидетелей», Алгоритмическая теория чисел (PDF) , Конспекты лекций по информатике, том. 877, Springer-Verlag, стр. 1–16, номер документа : 10.1007/3-540-58691-1_36, ISBN. 978-3-540-58691-3
19. Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . МР  0583518.
20. Берт-младший, Рональд Дж. (1996), «Дальнейшие исследования с использованием сильного вероятностного простого критерия» (PDF) , Mathematics of Computation , 65 (213): 373–381, Бибкод : 1996MaCom..65..373B, doi : 10.1090/S0025-5718-96-00695-3

Внешние ссылки

• Вайсштейн, Эрик В. «Сильный псевдопростой тест Рабина-Миллера». Математический мир .
• Интерактивная онлайн-реализация детерминированного варианта (пошаговое выполнение алгоритма)
• Апплет (немецкий)
• Тест Миллера-Рабина на простоту в C#
• Тест на простоту Миллера-Рабина в JavaScript с использованием арифметики произвольной точности