prime-check-naive.tex

\subsection{<<Наивный>> тест}\label{section-prime-check-naive}
\selectlanguage{russian}

<<Наивный>> тест состоит в проверке того, что число $n$ не делится на числа от $2$ до $\sqrt{n}+1$. Из определения простоты\index{число!простое} числа следует, что алгоритм будет являться корректным. Также очевидно, что алгоритм будет являться неполиномиальным относительно битовой длины числа $n$. Однако на нём хорошо показать определение <<свидетеля простоты>>, которое будет использоваться в алгоритмах в дальнейшем.

Будем называть число $a$ \emph{свидетелем простоты числа $n$ по наивному алгоритму}, если выполняется условие
\[
	n / a \notin \group{Z}.
\]

Теперь детерминированный <<наивный>> алгоритм можно сформулировать так: если все числа $a$ от 2 до $\sqrt{n}+1$ являются свидетелями простоты числа $n$ по наивному алгоритму, то число $n$ является простым\index{число!простое}. Иначе -- составным\index{число!составное}.

Детерминированный <<наивный>> тест можно превратить в вероятностный.

\begin{enumerate}
	\item Выберем случайным образом $k$ различных $a_1, a_2, \dots, a_k$ от 2 до $\sqrt{n}+1$.
	\item Проверим, являются ли они все свидетелями простоты числа $n$ по наивному алгоритму. 
	\item Если являются, то будем утверждать, что число $n$ является псевдопростым\index{число!псевдопростое} с вероятностью ошибки $\epsilon < \left( 1 - 1 / \sqrt{n} \right)^k$, иначе -- составным\index{число!составное}\footnote{Вероятность ошибки получена из вероятности <<наткнуться>> на \emph{несвидетеля простоты числа $n$ по наивному алгоритму}, которая для чисел от 2 до $\sqrt{n}+1$ не менее $1 / \sqrt{n}$ (минимальная вероятность для случая, когда $n = p \times q$, $p < \sqrt{n} < q$).}.
\end{enumerate}

Так как проверку каждого <<свидетеля>> можно сделать за одну операцию деления (полиномиальное число операций относительно длины числа $n$), то для заданного числа проверок $k$ данный вариант алгоритма будет являться доказанным, полиномиальным, но вероятностным. Кроме того, вероятность ошибки $\epsilon$ слишком велика. Для того, чтобы вероятность ошибки составляла менее 99\%, число проверок $k$ должно быть сравнимо по величине с $\sqrt{n}$.