Введение
Тест простоты
Тест простоты Миллера — Рабина или тест простоты Рабина — Миллера — это вероятностный тест простоты: алгоритм, который определяет, является ли данное число, вероятно, простым, подобно тесту простоты Ферма и тесту простоты Соловая — Страссена. Он имеет историческое значение в поиске детерминированного теста простоты за полиномиальное время. Его вероятностный вариант остаётся широко используемым на практике как один из самых простых и быстрых известных тестов. Гэри Л. Миллер открыл этот тест в 1976 году. Версия теста Миллера является детерминированной, но её корректность опирается на недоказанную расширенную гипотезу Римана. Майкл О. Рабин модифицировал его в 1980 году, чтобы получить безусловный вероятностный алгоритм.
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It is of historical significance in the search for a polynomial time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known. Gary L. Miller discovered the test in 1976. Miller's version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980.
Математические понятия
Аналогично тестам Ферма и Соловая-Штрассена, тест простоты Миллера-Рабина проверяет, выполняется ли для проверяемого числа определенное свойство, которое известно для простых чисел.
Выбор оснований
К счастью, ни одно составное число не является сильным псевдопростым ко всем основаниям одновременно (в отличие от теста простоты Ферма, для которого существуют псевдопростые числа Ферма ко всем основаниям: числа Кармайкла). Однако не существует простого способа найти свидетеля. Наивное решение — перебрать все возможные основания, что приводит к неэффективному детерминированному алгоритму. Тест Миллера является более эффективным вариантом этого (см. раздел «Тест Миллера» ниже). Другое решение — выбрать основание случайным образом. Это даёт быстрый вероятностный тест. Если n составное, то большинство оснований являются свидетелями, поэтому тест обнаружит n как составное с достаточно высокой вероятностью (см. раздел «Точность» ниже). Мы можем быстро снизить вероятность ложноположительного результата до произвольно малой величины, комбинируя результаты для стольких независимо выбранных оснований, сколько необходимо для достижения этой величины. Это тест Миллера — Рэбина. Кажется, что попытки с большим количеством оснований дают убывающую отдачу, поскольку если n является псевдопростым для некоторого основания, то оно, вероятно, будет псевдопростым и для другого основания. Обратите внимание, что a^(d) ≡ 1 (mod n) выполняется тривиально для a ≡ 1 (mod n), поскольку отношение сравнения совместимо с возведением в степень. И 1 = a^(d) = a^(2^(0)d) ≡ −1 (mod n) выполняется тривиально для a ≡ −1 (mod n), поскольку d нечётно, по той же причине. Именно поэтому случайные a обычно выбираются в интервале 1 < a < n − 1. Для тестирования произвольно больших n выбор оснований случайным образом необходим, поскольку мы не знаем распределение свидетелей и сильных лжецов среди чисел 2, 3, ..., n − 2. Однако предварительно выбранный набор из нескольких небольших оснований гарантирует идентификацию всех составных чисел до заранее вычисленного максимума. Этот максимум обычно значительно больше, чем сами основания. Это даёт очень быстрые детерминированные тесты для достаточно малых n (см. раздел «Тестирование на малых наборах оснований» ниже).
Доказательства
Вот доказательство того, что если n – простое число, то единственными квадратными корнями 1 по модулю n являются 1 и −1. Вот доказательство того, что если n – нечётное простое число, то оно является сильным вероятным простым по основанию a.
Сложность
Используя метод возведения в квадрат, время работы этого алгоритма составляет O(nk^2), где n — число, проверяемое на простоту, а k — количество выполненных итераций; таким образом, это эффективный алгоритм с полиномиальным временем работы. Умножение на основе БПФ (алгоритм Харви — Ховена) может уменьшить время работы до .