- Тест Миллера — Рабина
-
Тест Миллера — Рабина
Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.
Алгоритм был разработан Гари Миллером в 1976 и модифицирован Майклом Рабином в 1980 году.
Содержание
Свидетели простоты и теорема Рабина
Пусть m — нечётное число большее 1. Число m - 1 однозначно представляется в виде , где t нечётно. Целое число a, 1 < a < m, называется свидетелем простоты числа m, если выполняются два условия:
- m не делится на a;
- или существует целое k, , такое, что
Теорема Рабина утверждает, что составное нечётное число m имеет не более различных свидетелей простоты, где — функция Эйлера.
Алгоритм Миллера — Рабина
Алгоритм Миллера — Рабина параметризуется количеством раундов r. Рекомендуется брать r порядка величины log2(m), где m — проверяемое число.
Для данного m находятся такие целое число s и целое нечётное число t, что m − 1 = 2st. Выбирается случайное число a,1 < a < m. Если a не является свидетелем простоты числа m, то выдается ответ «m составное», и алгоритм завершается. Иначе, выбирается новое случайное число a и процедура проверки повторяется. После нахождения r свидетелей простоты, выдается ответ «m, вероятно, простое», и алгоритм завершается.
Алгоритм может быть записан на псевдокоде следующим образом:
Ввод: m > 2, нечётное натуральное число, которое необходимо проверить на простоту; r, параметр, определяющий точность теста. Вывод: составное, означает, что m точно составное; вероятно простое, означает, что m с высокой вероятностью является простым Представить m − 1 в виде 2s·t, где t нечётно, можно сделать последовательным делением m - 1 на 2. цикл А: повторить r раз: Выбрать случайное a в диапазоне [2, m − 2] x ← at mod m если x = 1 или x = m − 1 то перейти на следующую итерацию цикла А для r = 1 .. s − 1 x ← x2 mod m если x = 1 то вернуть составное если x = m − 1 то перейти на следующую итерацию цикла А вернуть составное вернуть вероятно простое
Из теоремы Рабина следует, что если r случайно выбранных чисел оказались свидетелями простоты числа m, то вероятность того, что m составное, не превосходит 4 - r.
Алгоритм Миллера
Изначальный алгоритм, предложенный Миллером, был детерминированным и состоял в проверке всех a от 2 до 70ln(m)2. Алгоритм Миллера гарантированно распознает простые и составные числа при условии выполнения обобщённой гипотезы Римана. Алгоритм Миллера — Рабина не зависит от справедливости обобщённой гипотезы Римана, но является вероятностным.
Сильно псевдопростые числа
Если число a является свидетелем простоты составного нечетного числа m, то число m в свою очередь называется сильно псевдопростым по основанию a. Если число m является сильно псевдопростым по основанию a, то оно также является псевдопростым по основанию a.
Ссылки
- «Как отличить составное число от простого», глава 4.4 из книги «Введение в криптографию» под редакцией В. В. Ященко
- С. Б. Гашков, «Упрощенное обоснование вероятностного теста Миллера — Рабина для проверки простоты чисел»
- Пример реализации на языке Python
Wikimedia Foundation. 2010.
Тест Миллера — Рабина вероятностный полиномиальный тест простоты. Тест Миллера Рабина позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера Рабина часто… … Википедия
Тест Миллера (теория чисел) — У этого термина существуют и другие значения, см. Тест Миллера. Не следует путать с «Тестом Миллера Рабина» вероятностным полиномиальным тестом простоты. Тест Миллера детерминированный полиномиальный тест простоты. В 1976 году Миллер… … Википедия
Тест Миллера-Рабина — … Википедия
Тест Миллера—Рабина — … Википедия
Тест Соловея — Штрассена вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью… … Википедия
Тест — (от слова англ. test) «испытание», «проверка» это метод изучения глубинных процессов деятельности человека, посредством его высказываний или оценок факторов функционирования системы управления Содержание 1 Программирование 2 Математика … Википедия
Тест простоты — Тест простоты алгоритм, который по заданному натуральному числу определяет, простое ли это число. Различают детерминированные и вероятностные тесты. Определение простоты заданного числа в общем случае не такая уж тривиальная задача. Только… … Википедия
Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может… … Википедия
Тест Агравала — В информатике тест Агравала Каяла Саксены (или тест AKS) это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентами Нираджем Каялом (англ … Википедия
Тест (значения) — Может, вы искали ?Тест (от слова en. test) испытание, проверка, анализ. Программирование * Тестирование программного обеспечения * Тест Тьюринга * Бета тестирование Тесты в биологических и биохимических исследованиях * Тест на ВИЧ *… … Википедия