prime-check-ferma.tex

\subsection{Тест Ферма}\label{section-prime-check-ferma}\index{тест!Ферма}
\selectlanguage{russian}

Многие тесты на простоту основаны на малой теореме Ферма\index{теорема!Ферма малая}~\cite{Vinberg:2008}: если $n$ -- простое число и $a$ -- целое число, не делящееся на $n$, то
\begin{equation}\label{eq:prime-check-ferma}
    a^{n-1} \equiv 1 \mod n.
\end{equation}

Можно сформулировать следующую <<обратную>> теорему. Если для некоторого $a: 1 < a < n$ не выполняется утверждение~\ref{eq:prime-check-ferma}, то число $n$ не является простым. На этой теореме основан следующий алгоритм, который и называется тестом Ферма.

Будем называть число $a$ \emph{свидетелем простоты числа $n$ по Ферма}, если для него выполняется~\ref{eq:prime-check-ferma}.

Тест Ферма для числа $n$ состоит в том, чтобы проверить, что все числа от $2$ до $n$ являются свидетелями простоты числа $n$ по Ферма. С точки зрения производительности, тест Ферма хуже <<наивного>> теста.

Вероятность встретить <<свидетеля непростоты>> аналогична <<наивному>> тесту в худшем случае (для чисел $n$, являющихся числами Кармайкла\index{число!Кармайкла}), а скорость проверки одного свидетеля много меньше, чем у <<наивного>> теста.