miller-rabins_test.tex

\subsection{Вероятностный тест Миллера -- Рабина}
\selectlanguage{russian}

Улучшение теста Ферма основано на следующем утверждении: для простого $p$, из сравнения
    \[ a^2 = 1 \mod p, \]
    \[ (a-1)(a+1) = 0 \mod p \]
следует одно из двух
\[ \left[ \begin{array}{l}
     a = 1 \mod p, \\
     a = -1 \mod p. \\
\end{array} \right. \]

Для того, чтобы использовать это утверждение, представим нечетное число $n$  в виде произведения
    \[ n-1 = 2^s r, \]
где $r$ -- нечетное. Тогда получим
    \[ a^{n-1} = (a^r)^{2^s} \mod n. \]
Вначале вычислим $a_0 = a^r \mod n$ и последовательно возведем в квадрат $s$ раз:
    \[ a_i = a_{i-1}^2 \mod n, ~ i = 1, \dots, s. \]
Очевидно, что сравнение $a_s = 1 \mod n$ может выполниться в одном из двух случаев:
\[ \left[ \begin{array}{l}
    \text{либо}~ a_0 = a^r = 1 \mod n, \\
    \text{либо одно из чисел}~ a_i = -1 \mod n, ~ i \in [0, s-1]. \\
\end{array} \right. \]
Если одно из условий для данного $a$  выполняется, то  <<$n$ \emph{возможно} простое>>; если не выполняется, то <<$n$ \emph{однозначно} составное>>. Оказывается, что для любого нечетного составного числа $n$ по меньшей мере $\frac{3}{4}$ всех чисел $a$ являются \emph{свидетелями непростоты} числа $n$, то есть, для которых тест не будет пройден.

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

Описание теста приведено в алгоритме $2$.

\begin{algorithm}[iht]
    \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]: ~ 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) \]
двоичных операций.

\example
В табл. \ref{tab-miller-rabin-sample} содержится пример теста Миллера--Рабина для $n = 169, ~ n-1 = 21 \cdot 2^3$.
\begin{table}[h!]
    \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