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

В Тест на простоту Миллера – Рабина или Тест на простоту Рабина-Миллера это тест на простоту: an алгоритм который определяет, является ли данное число вероятно, будет главным, аналогично Тест на простоту Ферма и Тест на простоту Соловея – Штрассена. Гэри Л. Миллер открыл его в 1976 году; Версия теста Миллера: детерминированный, но его правильность опирается на недоказанные расширенная гипотеза Римана.^[1] Майкл О. Рабин изменил его, чтобы получить безусловный вероятностный алгоритм в 1980 г.^[2] Часто говорят, что этот тест был открыт М. М. Артюховым в 1967 г.^[3] но это неверно: чтение статьи Артюхова (особенно его теоремы E) показывает, что он открыл Тест Соловея-Штрассена, а не тест Миллера-Рабина.

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

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

Первый лемма о площади корни единства в конечное поле Z/пZ, где п прост и п > 2. Конечно, 1 и −1 всегда дают 1 при возведении в квадрат по модулю п; назовите это банальный квадратные корни из 1. Нет нетривиальный квадратные корни из 1 по модулю п (частный случай результата, когда в поле многочлен нулей не больше, чем его степень). Чтобы показать это, предположим, что Икс квадратный корень из 1 по модулю п. Потом:

${\displaystyle x^{2}\equiv 1{\pmod {p}}}$

${\displaystyle (x-1)(x+1)\equiv 0{\pmod {p}}.}$

Другими словами, премьер п делит продукт (Икс − 1)(Икс + 1). К Лемма евклида он разделяет один из факторов Икс − 1 или Икс + 1, подразумевая, что Икс сравнимо с 1 или −1 по модулю п.

Теперь позвольте п быть первоклассным, и п > 2. Отсюда следует, что п − 1 четное, и мы можем записать его как 2^s·d, где s и d положительные целые числа и d странно. Для каждого а в (Z/пZ)*, либо

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

или

${\displaystyle a^{2^{r}\cdot d}\equiv -1{\pmod {n}}}$

для некоторого 0 ≤ r ≤ s − 1.

Чтобы показать, что одно из них должно быть правдой, вспомните Маленькая теорема Ферма, что для простого числа n:

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}.}$

По лемме выше, если мы продолжаем извлекать квадратные корни из а^п−1, мы получим либо 1, либо −1. Если мы получим −1, то второе равенство выполнено, и дело сделано. Если мы никогда не получим −1, то, когда мы вычеркнем все степени двойки, у нас останется первое равенство.

В случае, если п является премьер (n> 2), n-1 должно быть четным, чтобы мы могли написать:

${\displaystyle n-1=2^{r}d}$

когда d нечетное. Итак, мы пишем ${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$ является ${\displaystyle a^{n-1}-1\equiv 0{\pmod {n}}}$ , мы можем оценить термин:

${\displaystyle a^{2^{r}d}-1\equiv 0{\pmod {n}}}$

От личности ${\displaystyle x^{2}-y^{2}=(x-y)(x+y)}$ у нас есть:

${\displaystyle (a^{2^{r-1}d}-1)(a^{2^{r-1}d}+1)\equiv 0{\pmod {n}}}$

мы можем расширить термин как:

${\displaystyle (a^{2^{r-2}d}-1)(a^{2^{r-2}d}+1)(a^{2^{r-1}d}+1)\equiv 0{\pmod {n}}}$

и

${\displaystyle (a^{d}-1)(a^{d}+1)(a^{2d}+1)...(a^{2^{r-2}d}+1)(a^{2^{r-1}d}+1)\equiv 0{\pmod {n}}}$

если п является премьер, тогда ${\displaystyle {\displaystyle a^{d}\equiv 1{\pmod {n}}}}$ или ${\displaystyle {\displaystyle a^{d}\equiv -1{\pmod {n}}}}$ или ${\displaystyle {\displaystyle a^{2d}\equiv -1{\pmod {n}}}}$ или ${\displaystyle {\displaystyle a^{2^{2}d}\equiv -1{\pmod {n}}}}$ или или ${\displaystyle {\displaystyle a^{2^{r-1}d}\equiv -1{\pmod {n}}}}$ .

Тест на простоту Миллера – Рабина основан на контрапозитивный вышеуказанного требования. То есть, если мы сможем найти а такой, что

${\displaystyle a^{d}\not \equiv 1{\pmod {n}}}$

и

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$

для всех 0 ≤ r ≤ s - 1, то п не простое. Мы называем а а свидетель за составность п (иногда ошибочно называют сильный свидетель, хотя это определенное доказательство этого факта). Иначе а называется сильный лжец, и п это сильное вероятное простое число основать а. Термин «сильный лжец» относится к случаю, когда п является составным, но, тем не менее, уравнения выполняются, как и для простого числа.

Отметим, что Миллер – Рабин псевдопремы называются сильные псевдопреступности.

Каждая нечетная композиция п имеет много свидетелей а. Однако нет простого способа сгенерировать такой а известен. Решение - сделать тест вероятностный: выбираем ненулевое а в Z/пZ случайным образом и проверьте, является ли он свидетельством составности п. Если п составной, большинство вариантов для а будут свидетелями, и тест обнаружит п как составной с большой вероятностью. Тем не менее существует небольшая вероятность того, что нам не повезло и мы а который является сильным лжецом для п. Мы можем уменьшить вероятность такой ошибки, повторив тест для нескольких независимо выбранных а.

Однако выполнение тестов на многих базах дает убывающую отдачу, потому что если п является псевдопервичным основанием а, то более вероятно, что это псевдопробы для другой базы б.^[4]:§8

Для тестирования больших чисел обычно выбирают случайные основания а, так как априори неизвестно распределение свидетелей и лжецов по номерам 1, 2, ..., п - 1. В частности, Арно ^[5] дал 397-значный составной номер, для которого все основания а менее 307 - сильные лжецы. Как и ожидалось, это число было простым. Клен isprime () функция, в которой реализован тест Миллера – Рабина путем проверки конкретных оснований 2, 3, 5, 7 и 11. Однако выбор нескольких конкретных небольших оснований может гарантировать идентификацию композитов для п меньше некоторого максимума, определенного указанными основаниями. Этот максимум обычно довольно велик по сравнению с базами. Поскольку случайные базы не имеют такого детерминизма для малых п, конкретные базы лучше в некоторых обстоятельствах.

пример

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

• а^20·d мод п = 174⁵⁵ мод 221 = 47 1, п − 1
• а^21·d мод п = 174¹¹⁰ мод 221 = 220 = п − 1.

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

• а^20·d мод п = 137⁵⁵ мод 221 = 188 1, п − 1
• а^21·d мод п = 137¹¹⁰ мод 221 = 205 ≠ п − 1.

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

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

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

Вход # 1: п > 3, нечетное целое число, которое нужно проверить на простотуВход # 2: k, количество раундов тестирования для выполненияВывод: “составной" если п оказывается составным, "наверное премьер"Другое слово" п как 2р·d + 1 с d нечетное (путем разложения степеней двойки из п - 1) WitnessLoop: повторение k раз: выбрать случайное целое число а в диапазоне [2, п − 2]    Икс ← аd мод п    если Икс = 1 или Икс = п − 1 тогда        Продолжать WitnessLoop повторение р − 1 раз:        Икс ← Икс2 мод п        если Икс = п − 1 тогда            Продолжать WitnessLoop вернуть “составной”вернуть “наверное премьер”

Сложность

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

Точность

Ошибка, допущенная при проверке на простоту, измеряется вероятностью того, что составное число будет объявлено, вероятно, простым. Чем больше баз а пробовали, тем выше точность теста. Можно показать, что если п составно, то не более¹⁄₄ баз а сильные лжецы для п.^[2][6] Как следствие, если п составной, то работает k итерации теста Миллера – Рабина объявят п вероятно простое число с вероятностью не выше 4^−k.

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

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

Важно отметить, что во многих распространенных применениях этого алгоритма нас не интересует граница ошибки, описанная выше. Вышеупомянутая граница ошибки - это вероятность того, что составное число будет объявлено вероятным простым числом после k туры тестирования. Вместо этого нас часто интересует вероятность того, что после прохождения k раундов тестирования, проверяемое число фактически является составным числом. Формально, если мы назовем событие объявления п вероятный прайм после k раундов Миллера – Рабина Y_k, и мы называем событие, которое п составной Икс (и обозначим событие, которое п премьер ${\displaystyle {\overline {X}}}$), то полученная оценка дает нам ${\displaystyle P(Y_{k}|X)}$, а нас интересует ${\displaystyle P(X|Y_{k})}$. Теорема Байеса дает нам возможность связать эти две условные вероятности, а именно

${\displaystyle P(X|Y_{k})={\frac {P(Y_{k}|X)P(X)}{P(Y_{k}|X)P(X)+P(Y_{k}|{\overline {X}})P({\overline {X}})}}}$.

Это говорит нам о том, что вероятность, которая нас часто интересует, связана не только с 4^−k выше, но также вероятности, связанные с плотностью простых чисел в области около п.

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

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

Алгоритм Миллера – Рабина можно сделать детерминированным, попробовав все возможные а ниже определенного предела. Проблема в целом состоит в том, чтобы установить предел, чтобы тест оставался надежным.

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

Вход: п > 1, нечетное целое число, которое нужно проверить на простотуВывод: “составной" если п составной, "премьер"Другое слово" п как 2р·d +1 с d нечетное (путем разложения степеней двойки из п - 1) WitnessLoop: для всех а в диапазон [2, min (п−2, ⌊2(пер п)2⌋)]:    Икс ← аd мод п    если Икс = 1 или Икс = п − 1 тогда        Продолжать WitnessLoop повторение р − 1 раз:        Икс ← Икс2 мод п        если Икс = п − 1 тогда            Продолжать WitnessLoop вернуть “составной”вернуть “премьер”

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

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

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

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

Когда число п для тестирования мало, пробует все а <2 (ln п)² в этом нет необходимости, поскольку, как известно, достаточно гораздо меньшего числа потенциальных свидетелей. Например, Pomerance, Selfridge, Wagstaff.^[4] и Яешке^[9] подтвердили, что

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

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

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

Соренсон и Вебстер^[11] проверьте приведенное выше и вычислите точные результаты для этих более чем 64-битных результатов:

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

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

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

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

Вставив наибольший общий делитель вычислений в вышеупомянутый алгоритм, мы можем иногда получить коэффициент п вместо того, чтобы просто определить, что п составной. Это происходит, например, когда п является вероятной простой базой а но не сильная вероятная простая база а.^[17]:1402 Мы можем обнаружить этот случай в алгоритме, сравнив Икс во внутреннем цикле не только до -1, но и до 1.

Если на некоторой итерации 1 ≤ я < р внутреннего цикла алгоритм обнаруживает, что значение а^d·2я мод п переменной Икс равно 1, тогда, зная, что предыдущее значение Икс₀ = а^d·2s−1 переменной Икс проверено на отличие от ± 1, мы можем вывести, что Икс₀ является квадратным корнем из 1, который не равен ни 1, ни −1. Поскольку это невозможно, когда п простое число, отсюда следует, что п составной. Более того:

• поскольку Икс₀² ≡ 1 (мод п), мы знаем это п разделяет Икс₀² − 1 = (Икс₀ − 1)(Икс₀ + 1);
• поскольку Икс₀ ≢ ± 1 (мод. п), мы знаем это п не разделяет Икс₀ − 1 ни Икс₀ + 1.

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

Вход # 1: п > 3, нечетное целое число, которое нужно проверить на простотуВход # 2: k, количество раундов тестирования для выполненияВывод: (“несколько из”, м) если нетривиальный множитель м из п находится,        “составной" если п иначе считается составным, "наверное премьер"Другое слово" п как 2р·d +1 с d нечетное (путем разложения степеней двойки из п - 1) WitnessLoop: повторение k раз: выбрать случайное целое число а в диапазоне [2, п − 2]    Икс ← аd мод п    если Икс = 1 или Икс = п − 1 тогда        Продолжать WitnessLoop повторение р − 1 раз:        у ← Икс2 мод п        если у = 1:            вернуть (“несколько из”, НОД (Икс − 1, п))        Икс ← у        если Икс = п − 1 тогда            Продолжать WitnessLoop вернуть “составной”вернуть “наверное премьер”

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

Например, рассмотрим п = 341 и а = 2. Имеем п − 1 = 85·4. потом 2⁸⁵ мод 341 = 32. и 32² мод 341 = 1. Это говорит нам, что п является базой 2 псевдопростых чисел, но не сильной базой 2 псевдопервичных чисел. Вычисляя на этом этапе НОД, мы находим множитель 341: НОД (32 - 1, 341) = 31. Действительно, 341 = 11·31.

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

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

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

Вход # 1: б, количество бит результатаВход # 2: k, количество раундов тестирования для выполненияВывод: сильное вероятное простое число ппока Верно: выберите случайное нечетное целое число п в диапазоне [2б−1, 2б−1]    если тест Миллера – Рабина с входами п и k возвращает "наверное премьер” тогда        вернуть п

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

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

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

что справедливо для всех б ≥ 21 и k ≥ ​^б⁄₄. Эта оценка меньше 4^−k как только б ≥ 32.

Ряд криптографических библиотек используют тест Миллера-Рабина для генерации вероятных простых чисел. Альбрехт и др. смогли построить составные числа, которые некоторые из этих библиотек объявили простыми.^[19]

Примечания

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

внешняя ссылка

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