Тест на простоту Миллера – Рабина - Miller–Rabin primality test

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

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

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

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

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

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

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

• ${\ Displaystyle а ^ {д} \ эквив 1 {\ pmod {п}}}$;
• ${\ displaystyle a ^ {2 ^ {r} \ cdot d} \ Equiv -1 {\ pmod {n}}}$ для некоторого 0 ≤ r < s .

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

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

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

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

Выбор баз

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

Другое решение - случайный выбор базы. Это дает быстрый вероятностный тест . Когда n составное, большинство баз являются свидетелями, поэтому тест определит n как составное с достаточно высокой вероятностью (см. Раздел « Точность» ниже ). Мы можем быстро снизить вероятность ложного срабатывания до сколь угодно малой степени, объединив результаты стольких независимо выбранных баз, сколько необходимо для достижения указанной скорости. Это тест Миллера – Рабина. Количество пробных баз не зависит от n . Похоже, что попытка многих оснований дает убывающую отдачу, потому что, если n является псевдопервичным числом для некоторой базы, то более вероятно, что это будет псевдопервичным числом для другой базы.

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

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

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

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

Вот доказательство того, что если n - нечетное простое число, то это сильное вероятное простое число, лежащее в основе a .

Пример

Предположим, мы хотим определить, является ли n  = 221 простым. Мы пишем n −1 как 2 ² · 55, так что имеем s  = 2 и d  = 55. Мы случайным образом выбираем число a такое, что 1 <  a  <  n - 1, скажем, a = 174. Мы приступаем к вычислению:

• a ^{2 0 · d} mod n = 174 ⁵⁵ mod 221 = 47 1, n - 1
• a ^{2 1 · d} mod n = 174 ¹¹⁰ mod 221 = 220 = n - 1.

Поскольку 220 ≡ −1 mod n , либо 221 является простым числом, либо 174 является сильным обманщиком для 221. Мы пробуем другое случайное число a , на этот раз выбирая a = 137:

• a ^{2 0 · d} mod n = 137 ⁵⁵ mod 221 = 188 1, n - 1
• a ^{2 1 · d} mod n = 137 ¹¹⁰ mod 221 = 205 n - 1.

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

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

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

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: “composite” if n is found to be composite, “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Сложность

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

Точность

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

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

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

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

${\ Displaystyle \ 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)}} \ cdot {\ frac {\ Pr (P)} {\ Pr (\ lnot P)}}}} = {\ frac {1} {1 + {\ frac {1} {\ Pr (M \! R_ {k} \ mid \ lnot P)}} \ cdot {\ frac {\ Pr (P)} {1- \ Pr ( П)}}}}}$

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

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

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

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

Проба Миллера

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

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

Input: n > 1, an odd integer to be tested for primality
Output: “composite” if n is composite, “prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: for all a in the range [2, min(n−2, ⌊2(ln n)2⌋)]:
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        x ← x2 mod n
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “prime”

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

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

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

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

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

• если 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 ), и первый результат позже был показан с использованием различных методов у Цзян и Дэн:

• если 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.

Соренсон и Вебстер проверяют сказанное выше и вычисляют точные результаты для этих результатов, превышающих 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.

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

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

Варианты нахождения факторов

Вставляя вычисления наибольшего общего делителя в вышеупомянутый алгоритм, мы можем иногда получить множитель n вместо простого определения того, что n составное. Это происходит, например, когда n является вероятным основанием простого числа a, но не сильным основанием вероятного простого числа a . Мы можем обнаружить этот случай в алгоритме, сравнив x во внутреннем цикле не только с -1, но и с 1.

Если на некоторой итерации 1 ≤ i < r внутреннего цикла алгоритм обнаруживает, что значение a ^{d · 2 i} mod n переменной x равно 1, тогда, зная, что предыдущее значение x ₀ = a ^{d · 2 s −1} переменной x, как было проверено, отличается от ± 1, мы можем сделать вывод, что x ₀ является квадратным корнем из 1, который не является ни 1, ни −1. Поскольку это невозможно, когда n простое, это означает, что n составное. Кроме того:

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

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

Input #1: n > 3, an odd integer to be tested for primality
Input #2: k, the number of rounds of testing to perform
Output: (“multiple of”, m) if a non‐trivial factor m of n is found,
        “composite” if n is otherwise found to be composite,
        “probably prime” otherwise

write n as 2r·d + 1 with d odd (by factoring out powers of 2 from n − 1)
WitnessLoop: repeat k times:
    pick a random integer a in the range [2, n − 2]
    x ← ad mod n
    if x = 1 or x = n − 1 then
        continue WitnessLoop
    repeat r − 1 times:
        y ← x2 mod n
        if y = 1:
            return (“multiple of”, GCD(x − 1, n))
        x ← y
        if x = n − 1 then
            continue WitnessLoop
    return “composite”
return “probably prime”

Этот алгоритм не дает вероятностного алгоритма факторизации , потому что он способен находить множители только для чисел 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. Вычисляя GCD на этом этапе, мы находим множитель 341: НОД (32 - 1, 341) = 31. Действительно, 341 = 11 · 31 .

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

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

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

Input #1: b, the number of bits of the result
Input #2: k, the number of rounds of testing to perform
Output: a strong probable prime n

while True:
    pick a random odd integer n in the range [2b−1, 2b−1]
    if the Miller–Rabin test with inputs n and k returns “probably prime” then
        return 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) \ cdot \ left ({\ tfrac {1} {\ Pr (P)}} - 1 \ right) \ leq 4 ^ {- k} \ cdot \ left ({\ tfrac {\ ln 2} {2}} b-1 + {\ mathcal {O}} \ left (b ^ {- 1} \ right) \ right)}$

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

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

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

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

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

Примечания

использованная литература

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

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