prime-check-aks.tex

\subsection{Тест AKS}\label{section-prime-check-aks}\index{тест!AKS}
\selectlanguage{russian}

\emph{Первый} корректный, детерминированный и полиномиальный алгоритм проверки числа на простоту предложили Агравал, Каял и Саксена (\langen{Manindra Agrawal, Neeraj Kayal, Nitin Saxena}) в 2002 году~\cite{aks:2002}. Тест получил название AKS по фамилиям авторов. Сложность алгоритма для проверки $k$-битового числа равна
    \[ O(k^{6}). \]
К сожалению, несмотря на полиномиальность сложности теста, алгоритм очень медленный и не может быть применён для чисел с большой битовой длиной (в сотни, тысячи бит).

Основой теста является аналог малой теоремы Ферма для многочленов. Пусть числа $a$ и $p>1$ взаимно простые. В этом случае $p$ -- простое число тогда и только тогда, когда
\begin{equation}
    \label{eq:AKS1}
    (x - a)^p = x^p - a \mod p.
\end{equation}

Действительно, если $p$ -- простое\index{число!простое}, то биномиальные коэффициенты $\binom{p}{i},\ i = 1, \dots, p-1$ в разложении левой части делятся на $p$, то есть~$\binom{p}{i} = 0 \mod p$, а для последнего члена разложения $a^p$ выполняется $a^p = a \mod p$ по малой теореме Ферма\index{теорема!Ферма малая}. Следовательно, равенство верно.

Пусть число $p$ составное. Представим его в виде $p = A q^r$ с взаимно простыми $A$ и $q$ для некоторого простого $q$. Тогда коэффициент $\binom{p}{q}$ равен
\begin{multline*} 
\binom{p}{q}  = \frac{(A q^r) (A q^r - 1)(A q^r - 2) \dots (A q^r - q + 1)}{q (q-1)(q-2) \cdots 1} = \\ 
= \frac{A q^r}{q} \cdot \frac{A q^r - 1}{q-1} \cdot \frac{A q^r - 2}{q-2} \cdot ~\cdots~ \cdot \frac{A q^r - q + 1}{1}. 
\end{multline*}
Первый множитель $A q^r$ в числителе делится на $q$, далее идут \mbox{$q-1$} последовательно убывающих чисел, которые не делятся на $q$. Значит, $\binom{p}{q}$ не делится на $A q^r$,~$\binom{p}{q} \neq 0 \mod p$. Следовательно,
\[
(x - a)^p \neq x^p - a \mod p.
\]

Непосредственная проверка равенства \eqref{eq:AKS1} является трудоёмкой из-за необходимости проверить все коэффициенты. Рассмотрим следующую модификацию теста, которая тоже имеет полиномиальную сложность. Пусть для некоторого числа $r \nmid n$ ($r$ не делит $n$) выполняется равенство
\begin{equation}
    \label{eq:AKS2}
    (x - a)^p = x^p - a \mod (x^r-1, p).
\end{equation}
Другими словами, пусть
    \[ (x - a)^p - (x^p - a) = (x^r-1) \cdot f(x) + p \cdot g(x) \]
для некоторых многочленов $f(x)$ и $g(x)$. Тогда, либо $p$ -- простое, либо $p^2 = 1 \mod r$.

Описание теста AKS приведено в алгоритме~\ref{alg:aks}.

\begin{algorithm}[!ht]
    \caption{Детерминированный полиномиальный тест AKS\label{alg:aks}}
    \begin{algorithmic}
        \STATE Вход: число $n>1$ для проверки на простоту.
        \STATE Выход: \textsc{Составное} или \textsc{Простое}.
        \IF{~$n = a^b, ~a, b \in \group{N}, ~ b > 1$, для некоторых $a, b$~}
           \STATE \textbf{return} \textsc{Составное}.
        \ENDIF
        \STATE \textbf{Найти} наименьшее $r \in \group{N}$ с порядком $\ord_n(r) > \log_2^2 n$. Порядок числа $r$ по модулю $n$ определяется как минимальное число $ord_n(r) \in \group{N}$: \\
            \indent ~~~~~~~~~~~~~~~~~~~~~~~~~~~ $r^{\ord_n(r)} = 1 \mod n$.
        \IF{~$\gcd(a,n) \neq 1$ для некоторого $a \in \group{N}, ~a < r$~}
           \STATE \textbf{return} \textsc{Составное}.
        \ENDIF
        \FOR{~$a = 1$ ~\textbf{to}~ $2 \sqrt{r} \log_2 n$~}
            \IF{~$(x - a)^n ~\neq~ x^n - a \mod (x^r - 1, n)$~}
                \STATE \textbf{return} \textsc{Составное}.
            \ENDIF
        \ENDFOR
        \STATE \textbf{return} \textsc{Простое}
    \end{algorithmic}
\end{algorithm}