Тест на простоту Миллера – Рабина или тест на простоту Рабина – Миллера - это вероятностный тест на простоту : алгоритм, который определяет, может ли данное число быть простым , аналогично тесту на простоту Ферма и тесту на простоту Соловея – Штрассена .
Это имеет историческое значение для исследования детерминированного теста на простоту за полиномиальное время . Его вероятностный вариант по-прежнему широко используется на практике как один из самых простых и быстрых известных тестов.
Гэри Л. Миллер открыл этот тест в 1976 году; Версия теста Миллера детерминирована , но ее правильность основана на недоказанной расширенной гипотезе Римана . [1] Майкл О. Рабин модифицировал его, чтобы получить безусловный вероятностный алгоритм в 1980 году. [2] [a]
Математические понятия
Подобно тестам Ферма и Соловея – Штрассена, тест на простоту Миллера – Рабина проверяет, выполняется ли определенное свойство, которое, как известно, выполняется для простых значений, для проверяемого числа.
Сильные вероятные простые числа
Свойство следующее. Для данного нечетного целого числа n > 2 запишем n как 2 s ⋅ d + 1, где s и d - положительные целые числа, а d - нечетное. Рассмотрим целое число a , называемое основанием , такое, что 0 < a < n . Тогда n называется сильным вероятным простым числом, лежащим в основе a, если выполняется одно из этих соотношений сравнения :
- ;
- для некоторого 0 ≤ r < s .
Идея, лежащая в основе этого теста, заключается в том, что, когда n - нечетное простое число, оно проходит тест по двум причинам:
- по малой теореме Ферма ,(одно только это свойство определяет более слабое понятие вероятного простого числа в основе a , на котором основан тест Ферма);
- единственные квадратные корни из 1 по модулю n равны 1 и −1.
Следовательно, в противоположность этому , если n не является сильным вероятным простым числом для основания a , то n определенно составное, и a называется свидетелем составности n (иногда ошибочно называемым сильным свидетелем ).
Однако это свойство не является точной характеристикой простых чисел. Если n составное, оно, тем не менее, может быть сильным вероятным простым числом для основания a , и в этом случае оно называется сильным псевдопростом , а a - сильным лжецом .
Выбор баз
К счастью, ни одно составное число не является сильной псевдопервичностью для всех основ одновременно. Однако простой способ найти свидетеля неизвестен. Наивное решение - перепробовать все возможные основы, что приведет к неэффективному детерминированному алгоритму. Тест Миллера - более эффективный вариант этого (см. Раздел Тест Миллера ниже ).
Другое решение - выбрать базу наугад. Это дает быстрый вероятностный тест . Когда n составное, большинство баз являются свидетелями, поэтому тест определит n как составное с достаточно высокой вероятностью (см. Раздел « Точность» ниже ). Мы можем быстро снизить вероятность ложного срабатывания до сколь угодно малой степени, объединив результаты стольких независимо выбранных баз, сколько необходимо для достижения указанной скорости. Это тест Миллера – Рабина. Количество пробных баз не зависит от n . Похоже, что попытка многих оснований дает убывающую отдачу, потому что, если n является псевдопервичным числом для некоторой базы, то с большей вероятностью это будет псевдопервичным числом для другой базы. [4] : §8
Для проверки произвольно большого n выбор оснований наугад важен, так как мы не знаем распределения свидетелей и сильных лжецов среди чисел 1, 2,…, n −1 . [b]
Однако предварительно выбранный набор из нескольких небольших баз гарантирует идентификацию всех композитов до предварительно рассчитанного максимума. Этот максимум обычно довольно велик по сравнению с базами. Это дает очень быстрые детерминированные тесты для достаточно малых n (см. Ниже раздел « Тестирование на небольших наборах баз» ).
Доказательства
Вот доказательство того, что, когда n - нечетное простое число, единственные квадратные корни из 1 по модулю n равны 1 и −1.
Конечно, 1 и −1, возведенные в квадрат по модулю n , всегда дают 1. Осталось показать, что других квадратных корней из 1 по модулю n не существует . Это частный случай, применяемый здесь к многочлену X 2 - 1 над конечным полем Z / n Z , более общего факта, что многочлен над некоторым полем имеет не больше корней, чем его степень (эта теорема следует из существования евклидово деление многочленов ). Далее следует более элементарное доказательство. Предположим, что x - квадратный корень из 1 по модулю n . Потом:
Другими словами, n делит произведение ( x - 1) ( x + 1). . По лемме Евклида , поскольку n простое, оно делит один из множителей x - 1 или x + 1, из чего следует , что x сравнимо с 1 или −1 по модулю n .
Вот доказательство того, что если n - нечетное простое число, то это сильное вероятное простое число, лежащее в основе a .
По малой теореме Ферма:
Каждый член последовательности , является квадратным корнем из предыдущего члена. Поскольку первое слагаемое конгруэнтно 1, второе слагаемое является квадратным корнем по модулю n из 1. По предыдущей лемме он конгруэнтен либо 1, либо −1. Если он совпадает с -1, мы закончили. В противном случае он равен 1, и мы можем повторить рассуждение . В конце концов, либо один из членов конгруэнтен с -1, либо все они конгруэнтны 1, и, в частности, последний член, a d , равен.
Пример
Предположим, мы хотим определить, является ли n = 221 простым. Мы пишем n −1 как 2 2 · 55, так что имеем s = 2 и d = 55. Мы случайным образом выбираем число a такое, что 1 < a < n - 1, скажем, a = 174. Мы приступаем к вычислению:
- a 2 0 · d mod n = 174 55 mod 221 = 47 1, n - 1
- a 2 1 · d mod n = 174 110 mod 221 = 220 = n - 1.
Поскольку 220 ≡ −1 mod n , либо 221 является простым числом, либо 174 является сильным обманщиком для 221. Мы пробуем другой случайный a , на этот раз выбирая a = 137:
- a 2 0 · d mod n = 137 55 mod 221 = 188 1, n - 1
- a 2 1 · d mod n = 137 110 mod 221 = 205 n - 1.
Следовательно, 137 является свидетелем составности 221, а 174 на самом деле был ярым лжецом. Обратите внимание, что это ничего не говорит нам о множителях 221 (которые равны 13 и 17). Однако пример с 341 в следующем разделе показывает, как эти вычисления иногда могут давать коэффициент n .
Тест Миллера – Рабина
Алгоритм можно записать в псевдокоде следующим образом. Параметр k определяет точность теста. Чем больше количество раундов, тем точнее результат.
Ввод №1 : n > 3, нечетное целое число, которое нужно проверить на простоту. Ввод №2 : k , количество раундов тестирования для выполнения. Выход : « составной », если n оказывается составным, « вероятно, простое » в противном случаезапишите n как 2 r · d + 1 с нечетным d (путем факторизации степеней 2 из n - 1)WitnessLoop: повторить k раз : выберите случайное целое число a в диапазоне [2, n - 2] x ← a d mod n, если x = 1 или x = n - 1, затем продолжите WitnessLoop, повторите r - 1 раз : x ← x 2 mod n, если x = n - 1, затем продолжить. WitnessLoop, возврат « составной », возврат « вероятно, простой »
Сложность
При использовании повторного возведения в квадрат время работы этого алгоритма составляет O ( k log 3 n ) , где n - число, проверяемое на простоту, а k - количество выполненных раундов; таким образом, это эффективный алгоритм с полиномиальным временем. Умножение на основе БПФ может снизить время выполнения до O ( k log 2 n log log n log log log n ) = Õ ( k log 2 n ) .
Точность
Ошибка, допущенная при проверке на простоту, измеряется вероятностью того, что составное число будет объявлено, вероятно, простым. Чем больше оснований a испробовано, тем выше точность теста. Можно показать , что если п является составным, то не более 1 / 4 из оснований являются сильными лжецами для п . [2] [6] Как следствие, если n составное, то при выполнении k итераций теста Миллера – Рабина будет объявлено, что n вероятно простое с вероятностью не более 4 - k .
Это улучшение по сравнению с тестом Соловея – Штрассена , предел погрешности которого в наихудшем случае составляет 2 - k . Кроме того, тест Миллера-Рабина строго сильнее , чем тест Соловея-Штрассен в том смысле , что для каждого составного п , множество сильных лжецов для п является подмножеством множества Эйлера лжецов для п , и для многих п , то подмножество правильное.
Кроме того, для больших значений n вероятность того, что составное число будет объявлено простым, часто значительно меньше, чем 4 - k . Например, для большинства чисел n эта вероятность ограничена числом 8 - k ; доля чисел n, которые нарушают эту верхнюю границу, исчезает, когда мы рассматриваем большие значения n . [7] Следовательно, средний случай имеет гораздо лучшую точность, чем 4 - k , факт, который можно использовать для генерации вероятных простых чисел (см. Ниже ). Однако на такие улучшенные границы ошибок не следует полагаться для проверки простых чисел, распределение вероятностей которых не контролируется, поскольку криптографический злоумышленник может послать тщательно выбранную псевдопростую задачу, чтобы пройти проверку на простоту. [c] В таких контекстах можно полагаться только на предел ошибки наихудшего случая 4 - k .
Вышеупомянутая мера ошибки - это вероятность того, что составное число будет объявлено сильным вероятным простым числом после k раундов тестирования; математическими словами, это условная вероятность где P - это событие , при котором проверяемое число является простым, а MR k - это событие, когда оно проходит тест Миллера – Рабина за k раундов. Вместо этого нас часто интересует обратная условная вероятность: вероятность того, что число, объявленное сильным вероятным простым числом, на самом деле составное. Эти две вероятности связаны законом Байеса :
В последнем уравнении мы упростили выражение, используя тот факт, что все простые числа правильно указаны как сильные вероятные простые числа (тест не имеет ложноотрицательных результатов ). Опуская левую часть знаменателя , мы получаем простую оценку сверху:
Следовательно, эта условная вероятность связана не только с рассмотренной выше мерой ошибки, которая ограничена числом 4 - k, но и с распределением вероятностей входного числа. В общем случае, как было сказано ранее, это распределение контролируется криптографическим противником, таким образом, неизвестным, поэтому мы не можем сделать много выводов о. Однако в случае, когда мы используем тест Миллера – Рабина для генерации простых чисел (см. Ниже ), распределение выбирается самим генератором, поэтому мы можем использовать этот результат.
Детерминированные варианты
Проба Миллера
Алгоритм Миллера – Рабина можно сделать детерминированным, попробовав все возможные a ниже определенного предела. Принятие n в качестве предела означало бы O ( n ) испытаний, следовательно, время работы будет экспоненциально по отношению к размеру log n входных данных. Задача состоит в том, чтобы уменьшить время работы, насколько это возможно, при сохранении надежности теста.
Если тестируемое число п является составным, сильными лжецы взаимно простой с п содержатся в надлежащей подгруппе группы ( Z / п Z ) *, что означает , что если мы тестировать все A из набора , который генерирует ( Z / н Z ) *, один из них должен лежать вне указанной подгруппы, следовательно, должен свидетельствовать о составности n . Предполагая справедливость обобщенной гипотезы Римана (GRH), известно, что группа порождается своими элементами, меньшими, чем O (( ln n ) 2 ) , что уже отмечалось Миллером. [1] Константа, используемая в нотации Big O, была уменьшена до 2 Эриком Бахом . [9] Это приводит к следующему детерминированному алгоритму проверки простоты, известному как тест Миллера :
Вход : n > 1, нечетное целое число, которое нужно проверить на простоту. Выход : « составное », если n составное, « простое » в противном случае.запишите n как 2 r · d + 1 с нечетным d (путем факторизации степеней 2 из n - 1)WitnessLoop: для всех a в диапазоне [2, min ( n −2, ⌊2 (ln n ) 2 ⌋)]: x ← a d mod n, если x = 1 или x = n - 1, затем продолжить WitnessLoop, повторить r - 1 раз : x ← x 2 по модулю n, если x = n - 1, затем продолжить WitnessLoop return « композитный » возврат « простой »
Полная мощность обобщенной гипотезы Римана не требуется для обеспечения правильности теста: поскольку мы имеем дело с подгруппами четного индекса , достаточно предположить справедливость GRH для квадратичных характеров Дирихле . [6]
Время работы алгоритма, в мягких O обозначениях O ((журнал п ) 4 ) ( с использованием БПФ на основе умножения).
Тест Миллера на практике не используется. В большинстве случаев правильное использование вероятностного теста Миллера – Рабина или критерия простоты Бейли – PSW дает достаточную уверенность при гораздо более быстром беге. На практике это также медленнее, чем обычно используемые методы доказательства, такие как APR-CL и ECPP, которые дают результаты, не основанные на недоказанных предположениях. Для теоретических целей, требующих детерминированного алгоритма полиномиального времени, он был заменен тестом на простоту AKS , который также не полагается на недоказанные предположения.
Тестирование на небольших наборах баз
Когда число n, которое нужно проверить, мало, пробовать все a <2 (ln n ) 2 не нужно, поскольку известно, что достаточно гораздо меньших наборов потенциальных свидетелей. Например, Померанс, Селфридж, Вагстафф [4] и Яешке [10] подтвердили, что
- если 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 ), и первый результат позже был показан с использованием различных методов у Цзян и Дэн: [11]
- если 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 64 , достаточно проверить a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и 37.
Соренсон и Вебстер [12] проверяют вышеизложенное и вычисляют точные результаты для этих более чем 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.
Существуют и другие критерии такого рода, часто более эффективные (требуется меньшее количество баз), чем указанные выше. [13] [14] [15] [16] Они дают очень быстрые детерминированные тесты простоты для чисел в соответствующем диапазоне, без каких-либо предположений.
Существует небольшой список потенциальных свидетелей для каждого возможного размера ввода (не более b значений для b- битных чисел). Однако для всех составных чисел не может быть достаточного конечного набора базисов. Алфорд, Гранвиль и Померанс показали, что существует бесконечно много составных чисел n , наименьшее свидетельство составности которых не меньше (ln n ) 1 / (3ln ln ln n ) . [17] Они также эвристически утверждают, что наименьшее число w такое, что каждое составное число ниже n имеет свидетельство составности меньше, чем w, должно быть порядка Θ (log n log log n ).
Варианты нахождения факторов
Вставляя вычисления наибольшего общего делителя в вышеупомянутый алгоритм, мы можем иногда получить множитель n вместо простого определения того, что n составное. Это происходит, например, когда n является вероятным основанием простого числа a, но не сильным основанием вероятного простого числа a . [18] : 1402 Мы можем обнаружить этот случай в алгоритме, сравнив x во внутреннем цикле не только с -1, но и с 1.
Если на некоторой итерации 1 ≤ i < r внутреннего цикла алгоритм обнаруживает, что значение a d · 2 i mod n переменной x равно 1, тогда, зная, что предыдущее значение x 0 = a d · 2 s −1 переменной x, как было проверено, отличается от ± 1, мы можем сделать вывод, что x 0 является квадратным корнем из 1, который не является ни 1, ни −1. Поскольку это невозможно, когда n простое, это означает, что n составное. Более того:
- поскольку x 0 2 ≡ 1 (mod n ) , мы знаем, что n делит x 0 2 - 1 = ( x 0 - 1) ( x 0 + 1) ;
- поскольку x 0 ≢ ± 1 (mod n ) , мы знаем, что n не делит ни x 0 - 1, ни x 0 + 1 .
Отсюда мы заключаем, что A = GCD ( x 0 - 1, n ) и B = GCD ( x 0 + 1, n ) - нетривиальные (не обязательно простые) множители n (фактически, поскольку n нечетно, эти факторы взаимно просты и n = A · B ). Следовательно, если целью является факторинг, эти вычисления GCD могут быть включены в алгоритм с небольшими дополнительными вычислительными затратами. Это приводит к следующему псевдокоду, в котором выделен добавленный или измененный код:
Ввод №1 : n > 3, нечетное целое число, которое нужно проверить на простоту. Ввод №2 : k , количество раундов тестирования для выполнения. Выход : (« кратное », m ), если нетривиальный множитель m из n равен найдено, " составное ", если n в противном случае сочтено составным, « Вероятно, премьер » в противном случаезапишите n как 2 r · d + 1 с нечетным d (путем факторизации степеней 2 из n - 1)WitnessLoop: повторить k раз : выберите случайное целое число a в диапазоне [2, n - 2] x ← a d mod n, если x = 1 или x = n - 1, затем продолжите WitnessLoop, повторите r - 1 раз : y ← x 2 mod n, если y = 1 : return (« кратно », GCD ( x - 1, n )) x ← y, если x = n - 1, затем продолжить WitnessLoop return « составной » return « вероятно простой »
Этот алгоритм не дает вероятностного алгоритма факторизации , потому что он способен находить множители только для чисел n, которые являются псевдопервичными для основания a (другими словами, для чисел n, таких, что a n −1 1 mod n ). Для других чисел алгоритм возвращает только « составной » без дополнительной информации.
Например, рассмотрим n = 341 и a = 2. У нас n - 1 = 85 · 4. Тогда 2 85 mod 341 = 32. и 32 2 mod 341 = 1. Это говорит нам, что n является основанием 2 псевдопервичных чисел, но не сильным основанием псевдопервичных чисел 2. Вычисляя GCD на этом этапе, мы находим множитель 341: НОД (32 - 1, 341) = 31. Действительно, 341 = 11 · 31 .
Чтобы чаще находить множители, те же идеи можно применить к квадратным корням из -1 (или любого другого числа). Эту стратегию можно реализовать, используя знания из предыдущих раундов теста Миллера – Рабина. В этих раундах мы определили квадратный корень по модулю п -1, скажем R . Затем, когда x 2 mod n = n −1 , мы можем сравнить значение x с R : если x не является ни R, ни n - R , то GCD ( x - R , n ) и GCD ( x + R , n ) являются нетривиальными делителями n . [13]
Генерация вероятных простых чисел
Тест Миллера – Рабина можно использовать для генерации сильных вероятных простых чисел, просто вытягивая целые числа наугад до тех пор, пока тест не пройдет. Этот алгоритм почти наверняка завершается (так как на каждой итерации есть шанс вытянуть простое число). Псевдокод для генерации б - укусил сильные возможные простые числа (с наиболее значительным битом) выглядит следующим образом :
Вход №1 : b , количество битов результата. Ввод №2 : k , количество раундов тестирования, которые необходимо выполнить. Выход : сильное вероятное простое число n.в то время как True: выберите случайное нечетное целое число n в диапазоне [2 b −1 , 2 b −1], если тест Миллера – Рабина со входами n и k возвращает « вероятно, простое », затем верните n
Сложность
Конечно, время работы в худшем случае бесконечно, поскольку внешний цикл может никогда не завершиться, но это происходит с нулевой вероятностью. Согласно геометрическому распределению , ожидаемое количество розыгрышей составляет(повторное использование обозначений из ранее ).
Поскольку любое простое число проходит тест, вероятность того, что оно будет простым, дает грубую нижнюю границу вероятности прохождения теста. Если мы равномерно нарисуем нечетные целые числа в диапазоне [2 b −1 , 2 b −1], то получим:
где π - функция счета простых чисел . Используя асимптотическое разложение π (расширение теоремы о простых числах ), мы можем аппроксимировать эту вероятность, когда b возрастает до бесконечности. Мы нашли:
Следовательно, мы можем ожидать, что генератор выполнит не больше тестов Миллера – Рабина, чем число, пропорциональное b . Принимая во внимание сложность наихудшего случая каждого теста Миллера – Рабина (см. Ранее ), ожидаемое время работы генератора со входами b и k тогда ограничено O ( k b 4 ) (или Õ ( k b 3 ) с использованием Умножение на основе БПФ).
Точность
Мерой ошибки этого генератора является вероятность того, что он выведет составное число.
Используя связь между условными вероятностями (показанными в предыдущем разделе ) и асимптотическим поведением (показано как раз ранее), этой мере ошибки можно дать грубую верхнюю границу:
Следовательно, для достаточно больших b эта мера ошибки меньше, чем. Однако существуют гораздо лучшие границы.
Используя тот факт, что сам тест Миллера – Рабина часто имеет границу ошибки, намного меньшую, чем 4 - k (см. Ранее ), Дамгард , Ландрок и Померанс вывели несколько границ ошибки для генератора с различными классами параметров b и k . [7] Эти границы ошибок позволяют разработчику выбрать разумное значение k для достижения желаемой точности.
Одна из этих границ ошибки - 4 - k , которая выполняется для всех b ≥ 2 (авторы показали ее только для b ≥ 51, а Рональд Берте-младший завершил доказательство с оставшимися значениями 2 ≤ b ≤ 50 [19] ). Опять же, эту простую оценку можно улучшить для больших значений b . Например, еще одна граница, полученная теми же авторами:
которое выполняется для всех b ≥ 21 и k ≥ б ⁄ 4 . Эта оценка меньше 4- k, еслиb≥ 32.
Заметки
- ^ Тест Миллера-Рабина часто ошибочно говорят, были обнаружены М. Артюхов , как только 1967; чтение статьи Артюхова [3] (в частности, его теоремы E ) показывает, что он действительно открыл тест Соловея – Штрассена.
- ^ Например, в 1995 году Арно дает 397-значное составное число, для которого все основания меньше 307 являются сильными лжецами; функция Maple сообщила, что это число является простым
isprime()
, поскольку в ней реализован тест Миллера – Рабина с конкретными основаниями 2, 3, 5, 7 и 11. [5] - ^ Например, в 2018 году Альбрехт и др. смогли построить для многих криптографических библиотек, таких как OpenSSL и GNU GMP , составные числа, объявленные этими библиотеками простыми числами, тем самым продемонстрировав, что они не были реализованы с учетом противоборства. [8]
Рекомендации
- ^ Б Миллер, Гэри Л. (1976), "Римана гипотезы и тесты для простоты", журнал компьютерных и системных наук , 13 (3): 300-317, DOI : 10,1145 / 800116,803773 , S2CID 10690396
- ^ а б Рабин, Майкл О. (1980), «Вероятностный алгоритм для проверки простоты», Журнал теории чисел , 12 (1): 128–138, DOI : 10.1016 / 0022-314X (80) 90084-0
- ^ Артюхов, М.М. (1966–1967), «Некоторые критерии простоты чисел, связанные с малой теоремой Ферма», Acta Arithmetica , 12 : 355–364, MR 0213289
- ^ а б Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 .
- ^ Ф. Арно (август 1995 г.). «Построение чисел Кармайкла, которые являются сильными псевдопредставлениями на нескольких основаниях» . Журнал символических вычислений . 20 (2): 151–161. DOI : 10.1006 / jsco.1995.1042 .
- ^ а б Скуф, Рене (2004), "Четыре алгоритма проверки простоты" (PDF) , Алгоритмическая теория чисел: решетки, числовые поля, кривые и криптография , Cambridge University Press, ISBN 978-0-521-80854-5
- ^ а б Damgård, I .; Landrock, P. & Pomerance, C. (1993), "Средняя оценка случая ошибок для сильного вероятного простого теста" (PDF) , Математика вычислений , 61 (203): 177-194, Bibcode : 1993MaCom..61 .. 177D , DOI : 10,2307 / 2152945 , JSTOR 2152945
- ^ Мартин Р. Альбрехт; Джейк Массимо; Кеннет Дж. Патерсон; Юрай Соморовский (15 октября 2018 г.). Премия и предубеждение: проверка на примитивность в условиях состязательности (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
- ^ Jaeschke, Герхард (1993), "О сильном псевдопростом числе до нескольких оснований", Математика вычислений , 61 (204): 915-926, DOI : 10,2307 / 2153262 , JSTOR 2153262
- ^ Цзян, Юйпэн; Дэн, Инпу (2014). «Сильные псевдопредставления первых восьми оснований простых чисел» . Математика вычислений . 83 (290): 2915–2924. DOI : 10.1090 / S0025-5718-2014-02830-5 .
- ^ Соренсон, Джонатан; Вебстер, Джонатан (2015). «Сильные псевдопреступности к двенадцати основным основаниям». Математика вычислений . 86 (304): 985–1003. arXiv : 1509.00864 . Bibcode : 2015arXiv150900864S . DOI : 10.1090 / MCOM / 3134 . S2CID 6955806 .
- ^ а б Колдуэлл, Крис. «Поиск простых чисел и доказательство простоты - 2.3: сильная вероятностная простота и практический тест» . Основные страницы . Проверено 24 февраля 2019 года .
- ^ Чжан, Zhenxiang & Тан, Мин (2003), "Обнаружение сильного псевдопростого числа до нескольких оснований II.", Математика вычислений , 72 (44): 2085-2097, Bibcode : 2003MaCom..72.2085Z , DOI : 10,1090 / S0025-5718 -03-01545-X
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A014233 (наименьшее нечетное число, для которого проверка простоты Миллера – Рабина по основанию <= n-е простое число не выявляет составности)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ Изиковский, Войцех. «Детерминированные варианты критерия простоты Миллера – Рабина» . Проверено 24 февраля 2019 года .
- ^ Алфорд, WR ; Granville, A .; Померанс, К. (1994), «О трудности поиска надежных свидетелей» (PDF) , Лекционные заметки по компьютерным наукам , Springer-Verlag, 877 : 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 . Руководство по ремонту 0583518 .
- ^ Burthe Jr., Рональд Дж. (1996), «Дальнейшие исследования с сильным вероятным простым тестом» (PDF) , Mathematics of Computing , 65 (213): 373–381, Bibcode : 1996MaCom..65..373B , doi : 10.1090 / S0025-5718-96-00695-3
Внешние ссылки
- Вайсштейн, Эрик В. «Сильный псевдопервичный тест Рабина-Миллера» . MathWorld .
- Интерактивная онлайн-реализация детерминированного варианта (пошаговое выполнение алгоритма)
- Аплет (немецкий)
- Тест простоты Миллера – Рабина в C #
- Тест на простоту Миллера – Рабина в JavaScript с использованием арифметики произвольной точности