prime-check-miller.tex

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

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

Для того чтобы использовать это утверждение, представим чётное число $n - 1$ в виде произведения:
    \[ n-1 = 2^s r, \]
где $s$ является натуральным числом, а $r$ -- нечётным. Возьмём некоторое $a$, $1 < a < n$, и рассмотрим последовательность чисел (все вычисления делаются по модулю $n$)
\begin{equation}\label{eq:prime-check-miller-sequence}
	a^{r}, a^{2r}, a^{2^2 r}, a^{2^3 r}, \dots, a^{2^{s-1} r}, a^{2^s r} = a^{n-1} \mod n.
\end{equation}

Если число $n$ простое, то данная последовательность~\ref{eq:prime-check-miller-sequence} будет заканчиваться единицей. Причём в ряду~\ref{eq:prime-check-miller-sequence} перед единицей, если число $n$ простое, должно идти либо число $1$, либо $-1 \equiv n-1 \mod n$. Основываясь на этом свойстве, можно сформулировать определение свидетеля простоты.

Будем говорить, что число $a, 1 < a < n$, является \emph{свидетелем простоты числа $n$ по Миллеру}, если ряд~\ref{eq:prime-check-miller-sequence} либо начинается с единицы, либо содержит число $n-1$ и заканчивается единицей.

\example
Рассмотрим $n=4033$. Значение $s$ для $n$ равно $6$, то есть $n - 1 = 4032 = 63 \cdot 2^6$. То есть степени, в которые нужно будет возводить потенциальные свидетели простоты, равны:
\[ 63 \cdot 2^0, 63 \cdot 2^1, 63 \cdot 2^2, 63 \cdot 2^3, 63 \cdot 2^4, 63 \cdot 2^5, 63 \cdot 2^6= \]
\[ 63, 126, 252, 504, 1008, 2016, 4032. \]
\begin{itemize}
	\item Проверим, является ли число $a_1 = 1592$ свидетелем простоты числа $n = 4033$ по Миллеру. Вычислим степенной ряд:
		\[ a_1^{63}, a_1^{126}, a_1^{252}, a_1^{504}, a_1^{1008}, a_1^{2016}, a_1^{4032} \mod 4033 = \]
		\[ 1, 1, 1, 1, 1, 1, 1. \]
		Ряд состоит из всех единиц (начинается с единицы), поэтому $a_1 = 1592$ является свидетелем простоты числа $n = 4033$ по Миллеру.
	\item Проверим, является ли число $a_2 = 1094$ свидетелем простоты числа $n = 4033$ по Миллеру. Вычислим степенной ряд:
		\[ a_2^{63}, a_2^{126}, a_2^{252}, a_2^{504}, a_2^{1008}, a_2^{2016}, a_2^{4032} \mod 4033 =\]
		\[ 4032, 1, 1, 1, 1, 1, 1. \]
		Ряд начинается с числа $4032 \equiv -1 \mod 4033$ (содержит число $n-1$ и заканчивается единицей), поэтому $a_2 = 1094$ является свидетелем простоты числа $n = 4033$ по Миллеру.
	\item Проверим, является ли число $a_3 = 368$ свидетелем простоты числа $n = 4033$ по Миллеру. Вычислим степенной ряд:
		\[ a_3^{63}, a_3^{126}, a_3^{252}, a_3^{504}, a_3^{1008}, a_3^{2016}, a_3^{4032} \mod 4033 =\]
		\[ 142, 4032, 1, 1, 1, 1, 1. \]
		Ряд содержит число $4032 \equiv -1 \mod 4033$ (содержит число $n-1$ и заканчивается единицей), поэтому $a_3 = 368$ является свидетелем простоты числа $n = 4033$ по Миллеру.
	\item Проверим, является ли число $a_4 = 955$ свидетелем простоты числа $n = 4033$ по Миллеру. Вычислим степенной ряд:
		\[ a_4^{63}, a_4^{126}, a_4^{252}, a_4^{504}, a_4^{1008}, a_4^{2016}, a_4^{4032} \mod 4033 = \]
		\[ 591, 2443, 3442, 2443, 3442, 2443, 3442. \]
		Ряд не заканчивается на единицу, поэтому $a_4 = 955$ \emph{не} является свидетелем простоты числа $n = 4033$ по Миллеру.
	\item Проверим, является ли число $a_5 = 2593$ свидетелем простоты числа $n = 4033$ по Миллеру. Вычислим степенной ряд:
		\[ a_5^{63}, a_5^{126}, a_5^{252}, a_5^{504}, a_5^{1008}, a_5^{2016}, a_5^{4032} \mod 4033 =\]
		\[ 2256, 3923, 1, 1, 1, 1, 1. \]
		Ряд хотя и заканчивается на единицу, но перед первой единицей не находится $n-1$, то есть ряд не содержит число $n-1$ и не начинается на $1$, поэтому $a_4 = 2593$ \emph{не} является свидетелем простоты числа $n = 4033$ по Миллеру. Можно ещё сказать, что данный пример показал наличие в мультипликативной группе $\group{Z}_{4033}^{*}$ нетривиального \emph{делителя нуля}, то есть существование нетривиального корня уравнения $ x^2 \equiv 1 \mod 4033$, а именно числа 3923.
\end{itemize}
\exampleend

Вычисление ряда ~\ref{eq:prime-check-miller-sequence} делается не дольше, чем вычисление элемента $a^{n-1}$. Сначала вычисляем $a^{r}$, а все остальные элементы ряда получаем, возводя предыдущий элемент в квадрат.

В 1975 году Миллер (\langen{Gary L. Miller}, \cite{Miller:1975, Miller:1976}) показал, что если число $n$ является составным, и если верна расширенная гипотеза Римана\footnote{Гипотеза о распределении нулей дзета-функции Римана на комплексной плоскости.}, то между 2 и $O \left( \log^2 n \right)$ существует хотя бы одно число, не являющееся свидетелем простоты $n$. В 1985 году Эрик Бах (\langen{Eric Bach}, \cite{Bach:1990}) уменьшил границу до $2 \ln^2 n$. Что в результате приводит нас к тесту Миллера\index{тест!Миллера}.

\begin{enumerate}
	\item Возьмём все целые (можно простые) числа от $2$ до $2 \ln^2 n$ и проверим, являются ли они свидетелями простоты числа $n$ по Миллеру.
	\item Если являются, то число $n$ является простым\index{число!простое}, иначе -- составным\index{число!составное}.
\end{enumerate}

Данный тест является недоказанным (основывается на недоказанной гипотезе Римана), детерминированным и полиномиальным, так как и проверка одного свидетеля, и общее число требуемых свидетелей являются полиномиальными функциями от длины $n$. Тем не менее, число проверок в тесте остаётся достаточно большим (для чисел размером в 2048 бит это составляет более 250 тыс. проверок).