pseudo-primes_generation.tex

\subsection{Генерирование псевдопростых чисел}\label{section-pseudo-primes-generation}
\selectlanguage{russian}

Значительная часть криптосистем на открытых ключах основывается на использовании больших простых чисел. Однако получение таких чисел не является тривиальной операцией.

Генерировать большие простые числа заранее и сохранять их в некоторой таблице, например, для их последующего использования в качестве множителей модуля $n$ в криптосистеме RSA, небезопасно. Криптоаналитику для факторизации $n$ вместо перебора всех простых чисел в качестве кандидатов делителей $n$ будет достаточно перебрать заранее сохранённую таблицу возможных кандидатов. Однако и эффективной процедуры \emph{генерации} больших простых чисел, пригодных для использования в криптографии, неизвестно. Поэтому под генерацией больших простых чисел обычно используют и подразумевают процедуру \emph{поиска} больших простых чисел, описанную ниже.

\begin{enumerate}
	\item Выбрать большое (псевдо)случайное нечётное число нужной битовой длины.
	\item Проверить, является ли число простым\index{число!простое}.
	\item Если не является, то вернуться к п. 1. Иначе вернуть число как результат процедуры.
\end{enumerate}

Дополнительной проблемой является тот факт, что быстрые и качественные алгоритмы проверки на простоту также неизвестны. Все существующие алгоритмы можно классифицировать следующим образом:
\begin{itemize}
	\item Алгоритмы <<\emph{доказанные}>> и <<\emph{недоказанные}>>. Корректность <<доказанных>> алгоритмов основывается на доказанных математических утверждениях. Остальные алгоритмы могут приводиться без доказательств либо могут быть основаны на недоказанных математических гипотезах, таких как гипотеза Римана. Существуют также \emph{некорректные} алгоритмы, для которых доказано, что результат их работы для некоторых чисел ошибочен.
	\item Некоторые алгоритмы для своей работы используют случайные числа, из-за чего результат их работы может отличаться от запуска к запуску. Такие алгоритмы называются \emph{вероятностными}, остальные -- \emph{детерминированными}. Для вероятностных алгоритмов существует вероятность ошибки $\epsilon$, которая может являться функцией от дополнительного аргумента алгоритма (например, от числа раундов). В зависимости от теста, ошибка может быть как на вероятность объявить простое число составным, так и на вероятность объявить составное число простым.
	\item По производительности алгоритмы проверки чисел на простоту разделяют на \emph{полиномиальные} и \emph{неполиномиальные} от длины числа. Количество операций для полиномиального алгоритма не должно превышать значение некоторого полинома от битовой длины числа.
\end{itemize}

Идеальный алгоритм проверки чисел на простоту должен быть доказанным, детерминированным и полиномиальным. Кроме ограничений на рост количества операций (<<полиномиальный>>) алгоритм должен быстро работать для тех чисел, которые используются уже сейчас (2000 бит и выше) на современных персональных компьютерах. К сожалению, такие алгоритмы неизвестны.

\begin{itemize}
	\item <<Наивный>> алгоритм (разд.~\ref{section-prime-check-naive}) является доказанным, детерминированным, но неполиномиальным (экспоненциальным) и медленным.
	\item Тест Ферма\index{тест!Ферма} (разд.~\ref{section-prime-check-ferma}) также является доказанным, детерминированным, но неполиномиальным и медленным.
	\item Тест Миллера\index{тест!Миллера} (разд.~\ref{section-prime-check-miller}) является детерминированным, полиномиальным, но недоказанным и относительно медленным.
	\item Тест Миллера~---~Рабина\index{тест!Миллера~---~Рабина} (разд.~\ref{section-prime-check-miller-rabin}) является доказанным, полиномиальным, относительно быстрым, но вероятностным. Существует вероятность, что он объявит составное число простым.
	\item Тест AKS (разд.~\ref{section-prime-check-aks}) является доказанным, детерминированным, полиномиальным, но для существующей технологической базы медленным.
\end{itemize}

В настоящий момент для проверки числа на простоту используют комбинацию <<наивного>> алгоритма и теста Миллера~---~Рабина\index{тест!Миллера~---~Рабина}.

\begin{enumerate}
	\item Выбрать параметр <<уверенности>> (\langen{certainty}), который вместе с требуемой битовой длиной числа будет являться входом алгоритма.
	\item Выбрать большое (псевдо)случайное нечётное число $n$ нужной битовой длины.
	\item Проверить, является ли число $n$ простым по <<наивному>> тесту до некоторого числа $m \ll n$ (часто -- константа алгоритма).
	\item Проверить, является ли число $n$ простым по тесту Миллера~---~Рабина с числом раундов, которое зависит от значения параметра <<уверенности>>.
	\item Если число $n$ прошло все тесты, то оно является выходом алгоритма. Иначе возвращаемся к п. 2.
\end{enumerate}

Числа, полученные с помощью подобного алгоритма (или любого другого, если для проверки на простоту используются вероятностные алгоритмы), называются \emph{псевдопростыми}\index{число!псевдопростое}.

Согласно формулам из предыдущего раздела, в среднем за $\ln n$ попыток встретится простое число. Если выбирать только нечётные числа, то среднее число попыток $\frac{\ln n}{2}$. Однако если выбирать такие числа, которые гарантированно не имеют малых делителей (<<просеивание чисел>>), то значительно повышаются шансы, что это число окажется простым. Например для $L = 10^4$ вероятность, что 1024-битовое нечётное число
    \[ n \approx 2^{1024} \]
окажется простым, повышается в
    \[ \frac{1}{P(10^4)} \approx 10 \]
раз. В среднем, каждое
    \[ \frac{\ln n}{2} \cdot P(L) \approx \frac{710}{2} \frac{1}{10} \approx 36 \]
нечётное число может быть простым вместо каждого $\frac{\ln n}{2} \approx 355$ числа, если нечётные числа выбирать без ограничений (без просеивания).

В этом случае средняя сложность генерирования $k$-битового псевдопростого числа имеет порядок:
    \[ O \left( \frac{\ln n}{2} \cdot \frac{1}{P(L)} \cdot \left( t k^3 \right) \right) = O(t k^4). \]