fermas_test.tex

\subsection{Тест Ферма}
\selectlanguage{russian}

Многие \emph{тесты на простоту} основаны на малой теореме Ферма: если $a$ и $n$ взаимно простые числа, то
    \[ a^{n-1} = 1 \mod n. \]

\textbf{Тестом Ферма}\index{тест!Ферма} на простоту числа $n$ по основанию $a$ называется процедура:
\begin{itemize}
    \item если для взаимно простых основания $a$ и модуля $n$ выполняется $a^{n-1} = 1 \mod n$, то $n$ \emph{может быть} простым,
    \item если $a^{n-1} \ne 1 \mod n$, то $n$ -- \emph{однозначно} составное.
\end{itemize}

Тесты есть \emph{детерминированные}, которые перебирают все $a$ до некоторой границы $a < A$, либо \emph{вероятностные}, которые проверяют тестом Ферма несколько псевдослучайных чисел $a$.

\textbf{Псевдопростым}\index{псевдопростое число} числом называется число, про которое не известно, является ли оно простым или нет, и удовлетворяющее вероятностному тесту на простоту с вероятностью ошибки теста меньше заданного $\epsilon$.

Оказывается, есть числа, которые удовлетворяют тесту Ферма для любого основания $a$. Числом Кармайкла\index{Кармайкла, число} называется составное число $n$, для которого тест Ферма выполняется для всех оснований $a$, взаимно простых с $n$. Первое число Кармайкла $561 = 3 \cdot 11 \cdot 17$. Чисел Кармайкла бесконечно много, но встречаются редко.

\example
Тест Ферма для числа Кармайкла $n = 561$ и взаимно простого с ним основания $a = 2$, приводится ниже:
\[
    n - 1 = 560 = 35 \cdot 2^4,
\] \[ \begin{array}{ll}
    2^{35} & =~ 2^1 \cdot 2^2 \cdot 2^{4 \cdot 0} \cdot 2^{8 \cdot 0} \cdot 2^{16 \cdot 0} \cdot 2^{32} ~= \\
        & =~ 2 \cdot 4 \cdot 16^0 \cdot 256^0 \cdot 460^0 \cdot 103 ~= \\
        & =~ 263 \mod 561, \\
\end{array} \] \[ \begin{array}{ll}
    2^{560} & =~ \left( 2^{35} \right)^{2^4} ~=~ 263^{2^4} ~= \\
        & =~ 166^{2^3} ~=~ 67^{2^2} ~=~ 1^{2} ~=~ 1 \mod 561.
\end{array} \]
\exampleend