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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выбор баз

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

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

Обратите внимание, что $a d \equiv 1 (mod n)$ выполняется тривиально для $a \equiv 1 (mod n)$ , поскольку отношение конгруэнтности совместимо с возведением в степень . И $a d = a 20 d \equiv -1 (mod n)$ выполняется тривиально для $a \equiv -1 (mod n) ,$ поскольку $d$ нечетно, по той же причине. Вот почему случайные $a$ обычно выбираются в интервале $1 < a < n - 1$ .

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

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

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

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

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

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

(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 — нечетное положительное целое число, по малой теореме Ферма:

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

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

Пример

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

Сказать : $а=174$

${\begin{aligned}a^{{s^{0}}d}{\text{ mod }}n\rightarrow &174^{{2^{0}}55}{\text{ mod }}221\equiv 174^{55}\equiv 47{\text{. Поскольку }}47\neq 1{\text{ и }}47\neq n-1{\text{, мы продолжаем.}}\\&174^{{2^{1}}55}{\text{ mod }}221\equiv 174^{110}\equiv 220=n-1\end{aligned}}$

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

${\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 .

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

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

Алгоритм можно записать в псевдокоде следующим образом. Параметр 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 ² mod n  если  y = 1 и x ≠ 1 и x ≠ n − 1 , то  # нетривиальный квадратный корень из 1 по модулю n  вернуть « составной » x ← y  если  y ≠ 1 , то  вернуть « составной » вернуть « вероятно простой »

Сложность

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

Точность

Ошибка, допущенная тестом на простоту, измеряется вероятностью того, что составное число будет объявлено, вероятно, простым. Чем больше оснований a опробовано, тем выше точность теста. Можно показать, что если 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 раундами. Вместо этого нас часто интересует обратная условная вероятность : вероятность того, что число, объявленное сильным вероятным простым числом, на самом деле является составным. Эти две вероятности связаны законом Байеса : $\Pr(M\!R_{k}\mid \lnot P)$ $\Pr(\lnot P\mid M\!R_{k})$

{\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}}

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

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

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

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

тест Миллера

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

Если проверяемое число n является составным, сильные лжецы a, взаимно простые с n, содержатся в собственной подгруппе группы ( Z / n Z )*, что означает, что если мы проверяем все a из набора, который порождает ( Z / n Z )*, один из них должен лежать вне указанной подгруппы, следовательно, должен быть свидетелем составности n . Предполагая истинность расширенной гипотезы Римана (ERH), известно, что группа порождается ее элементами, меньшими, чем $O(( ln n) 2)$ , что уже было отмечено Миллером. ^[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 ) ² ⌋)]: x ← a ^d mod n  повторить  s  раз : y ← x ² mod n  если  y = 1 и x ≠ 1 и x ≠ n − 1 , то  # нетривиальный квадратный корень из 1 по модулю n  вернуть « составной » x ← y  если  y ≠ 1 , то  вернуть « составной » вернуть « простой »

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

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

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

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

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

если n < 2047, достаточно проверить 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 и 1662 803;
если 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.

Используя работу Фейтсмы и Голуэя, которые в 2010 году перечислили все псевдопростые числа с основанием 2, это число было расширено (см. 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 2 \equiv 1 (mod n)$ , мы знаем, что n делит $x 2 - 1 = (x - 1)(x + 1)$ ;
поскольку $x ≢ \pm1 (mod n)$ , мы знаем, что n не делит $x - 1$ и $x + 1$ .

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

Вход № 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 ² mod n  если  y = 1 и x ≠ 1 и x ≠ n − 1 then  # нетривиальный квадратный корень из 1 по модулю n  вернуть (« кратное », gcd( x − 1, n ))  x ← y  если  y ≠ 1 then  вернуть « составной » вернуть « вероятно простой »

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

Например, рассмотрим n = 341 и a = 2. Имеем $n - 1 = 85 \times 4.$ Тогда $285 mod 341 = 32$ и $322 mod 341 = 1.$ Это говорит нам, что n является псевдопростым числом с основанием 2, но не сильным псевдопростым числом с основанием 2. Вычисляя gcd на этом этапе, мы находим множитель 341: $gcd(32 - 1, 341) = 31.$ Действительно, $341 = 11 \times 31$ .

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

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

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

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

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

Сложность

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

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

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

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

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

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

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

Точность

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

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

\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 эта мера ошибки меньше . Однако существуют гораздо лучшие границы. ${\tfrac {\ln 2}{2}}4^{-k}b$

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

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

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

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

Примечания

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

Ссылки

^ ab Miller, Gary L. (1976), «Гипотеза Римана и тесты на простоту», Журнал компьютерных и системных наук , 13 (3): 300–317, doi :10.1145/800116.803773, S2CID 10690396
^ ab Рабин, Майкл О. (1980), «Вероятностный алгоритм проверки простоты», Журнал теории чисел , 12 (1): 128–138, doi :10.1016/0022-314X(80)90084-0
^ Артюхов, ММ (1966–1967), «Некоторые критерии простоты чисел, связанные с малой теоремой Ферма», Acta Arithmetica , 12 : 355–364, MR 0213289
^ ab Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф, младший (июль 1980 г.). "Псевдопростые числа до 25 ⋅ 109" (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
^ Ф. Арно (август 1995 г.). «Построение чисел Кармайкла, являющихся сильными псевдопростыми числами с несколькими основаниями». Журнал символических вычислений . 20 (2): 151–161. doi : 10.1006/jsco.1995.1042 .
^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2009) [1990]. «31». Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 968–971. ISBN 0-262-03384-4.
^ ab Schoof, René (2004), "Четыре алгоритма проверки простоты" (PDF) , Алгоритмическая теория чисел: решетки, числовые поля, кривые и криптография , Cambridge University Press, ISBN 978-0-521-80854-5
^ ab Damgård, I. ; Landrock, P. & Pomerance, C. (1993), "Оценки средней ошибки для сильного вероятного простого теста" (PDF) , Mathematics of Computation , 61 (203): 177–194, Bibcode :1993MaCom..61..177D, doi :10.2307/2152945, JSTOR 2152945
^ Мартин Р. Альбрехт; Джейк Массимо; Кеннет Г. Патерсон; Юрай Соморовски (15 октября 2018 г.). Prime and Prejudice: Primality Testing Under Adversarial Conditions (PDF) . Конференция ACM SIGSAC по компьютерной и коммуникационной безопасности 2018 г. Торонто: Ассоциация вычислительной техники . стр. 281–298. doi :10.1145/3243734.3243787.
^ Бах, Эрик (1990), «Явные границы для проверки простоты и связанных с этим проблем», Математика вычислений , 55 (191): 355–380, Bibcode : 1990MaCom..55..355B, doi : 10.2307/2008811 , JSTOR 2008811
^ Йешке, Герхард (1993), «О сильных псевдопростых числах с несколькими основаниями», Математика вычислений , 61 (204): 915–926, doi : 10.2307/2153262 , JSTOR 2153262
^ Цзян, Юпэн; Дэн, Инпу (2014). «Сильные псевдопростые числа по первым восьми простым основаниям». Математика вычислений . 83 (290): 2915–2924. doi : 10.1090/S0025-5718-2014-02830-5 . S2CID 33599405.
^ Соренсон, Джонатан; Вебстер, Джонатан (2015). «Сильные псевдопростые числа по двенадцати простым основаниям». Математика вычислений . 86 (304): 985–1003. arXiv : 1509.00864 . Bibcode : 2015arXiv150900864S. doi : 10.1090/mcom/3134. S2CID 6955806.
^ ab Caldwell, Chris. "Finding primes & proving primeality — 2.3: Strong likely-primality and a practical test". The Prime Pages . Получено 24 февраля 2019 г.
^ Чжан, Чжэньсян и Тан, Мин (2003), «Нахождение сильных псевдопростых чисел по нескольким основаниям. II», Математика вычислений , 72 (44): 2085–2097, Bibcode : 2003MaCom..72.2085Z, doi : 10.1090/S0025-5718-03-01545-X
^ Слоан, Н. Дж. А. (ред.). "Последовательность A014233 (Наименьшее нечетное число, для которого тест Миллера–Рабина на простоту по основаниям <= n-го простого числа не выявляет составность)". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
^ Изыковский, Войцех. "Детерминированные варианты теста простоты Миллера–Рабина" . Получено 24 февраля 2019 г. .
^ Alford, WR ; Granville, A .; Pomerance, C. (1994), «О трудности поиска надежных свидетелей», Алгоритмическая теория чисел (PDF) , Lecture Notes in Computer Science, т. 877, Springer-Verlag, стр. 1–16, doi :10.1007/3-540-58691-1_36, ISBN 978-3-540-58691-3
^ Роберт Бейли; Сэмюэл С. Вагстафф, младший (октябрь 1980 г.). «Псевдопростые числа Лукаса» (PDF) . Математика вычислений . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR 0583518.
^ Берт-младший, Рональд Дж. (1996), «Дальнейшие исследования с сильным тестом на вероятное простое число» (PDF) , Математика вычислений , 65 (213): 373–381, Bibcode : 1996MaCom..65..373B, doi : 10.1090/S0025-5718-96-00695-3

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

В Реализации алгоритма Wikibook есть страница на тему: Тестирование на простоту.

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