prime-check-miller-rabin.tex

\subsection{Тест Миллера~---~Рабина}\label{section-prime-check-miller-rabin}\index{тест!Миллера~---~Рабина}
\selectlanguage{russian}

В 1980 году Рабин (\langen{Michael O. Rabin}, \cite{Rabin:1980}) обратил внимание на то, что у нечётного составного числа $n$ количество свидетелей простоты $1 < a < n$ по Миллеру не превышает $n/4$. Это означает, что если число $1 < a < n$ является свидетелем простоты числа $n$ по Миллеру, то число $n$ является простым с вероятностью ошибки не более чем $1/4$. Что приводит нас к вероятностному тесту Миллера~---~Рабина.

Тест Миллера~---~Рабина\index{тест!Миллера~---~Рабина} состоит в проверке $t$ случайно выбранных чисел $1 < a < n$. Если для всех $t$ чисел $a$ тест пройден, то $n$ называется псевдопростым\index{число!псевдопростое}, и вероятность того, что число $n$ не простое, имеет оценку:
    \[ P_{error} < \left( \frac{1}{4} \right)^t. \]
Если для какого-то числа $a$ тест не пройден, то число $n$ точно составное\index{число!составное}.

Описание теста приведено в алгоритме~\ref{miller-rabin}.

\begin{algorithm}[ht]
    \caption{Вероятностный тест Миллера~---~Рабина проверки числа на простоту\label{miller-rabin}}
    \begin{algorithmic}
        \STATE Вход: нечётное $n>1$ для проверки на простоту и $t$ -- параметр надёжности.
        \STATE Выход: \textsc{Составное} или \textsc{Псевдопростое}.
        \STATE $n - 1 = 2^s r, ~ r$ -- нечётное.
        \FOR{~$j = 1$ ~\textbf{to}~ $t$~}
            \STATE Выбрать случайное число $a \in [2, n-2]$.
            \IF{~$(a_0 = a^r ~\neq~ \pm 1 \mod n)$ ~\textbf{and} \\
            \indent ~~~~~~ $(\forall i \in [1, s-1] \rightarrow a_i = a_0^{2^i} ~\neq~ -1 \mod n)$~}
               \STATE \textbf{return} \textsc{Составное}.
           \ENDIF
        \ENDFOR
       \STATE \textbf{return} \textsc{Псевдопростое} с вероятностью ошибки $P_{error} < \left( \frac{1}{4} \right)^t$.
    \end{algorithmic}
\end{algorithm}

Сложность алгоритма Миллера~---~Рабина для $k$-битового числа $n$ имеет порядок
    \[ O(t k^3) \]
двоичных операций, где $t$ -- количество раундов.

\example
В таблице~\ref{tab-miller-rabin-sample} содержится пример теста Миллера~---~Рабина для $n = 169, ~ n-1 = 21 \cdot 2^3$.
\begin{table}[!ht]
    \centering
    \caption{Пример теста Миллера~---~Рабина для $n = 169$ и четырёх оснований $a$: 19, 22, 23, 2\label{tab-miller-rabin-sample}}
    \resizebox{\textwidth}{!}{ \begin{tabular}{||c|l|p{0.35\textwidth}||}
        \hline
        $a$ & $a_i \mod n$ & Вывод \\
        \hline \hline
        $19$ & $a_0 = a^r = 19^{21} = 70 \neq \pm 1 \mod 169$ & Возводим далее в квадрат \\
             & $a_1 = a_0^2 = -1 \mod 169$ & \textsc{Псевдопростое по основанию} $a=19$ \\
        \hline \hline
        $22$ & $a_0 = a^r = 22^{21} = 1 \mod 169$ & \textsc{Псевдопростое по основанию} $a=22$\\
        \hline \hline
        $23$ & $a_0 = a^r = 23^{21} = -1 \mod 169$ & \textsc{Псевдопростое по основанию} $a=23$\\
        \hline \hline
        $2$  & $a_0 = a^r = 2^{21} = 31 \neq \pm 1 \mod 169$ & Возводим далее в квадрат \\
             & $a_1 = a_0^2 = 116 \neq -1 \mod 169$ & Возводим далее в квадрат\\
             & $a_{s-1=2} = a_1^2 = 105 \neq -1 \mod 169$ & \textsc{Составное} \\
        \hline
    \end{tabular} }
\end{table}
\exampleend

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