linear-congruential-generator.tex

\section{Линейный конгруэнтный генератор}\label{section-linear-congruential-generator}\index{генератор!линейный конгруэнтный}
\selectlanguage{russian}

Алгоритм был предложен Лемером (\langen{Derrick Henry Lehmer},~\cite{Lehmer:1951:1, Lehmer:1951:2}) в 1949 году. Линейный конгруэнтный генератор основывается на вычислении последовательности $x_n, x_{n+1}, \dots$, такой что:
	\[x_{n+1} = a \cdot x_n + c \mod m.\]

Числа $a, c, m$, $ 0 < a < m, 0 < c < m$, являются параметрами алгоритма.

\example
Для параметров $a = 2, c = 3, m = 5$ и начального состояния $x_0 = 1$ получаем последовательность: $0, 3, 4, 1, 0, \dots$
\exampleend

Максимальный период ограничен значением $m$. Но максимум периода достигается тогда и только тогда, когда~\cite[Линейный конгруэнтный метод]{Knuth:2001:2}:

\begin{itemize}
	\item числа $c$ и $m$ взаимно просты\index{числа!взаимно простые};
	\item число $a - 1$ кратно каждому простому делителю числа $m$;
	\item число $a - 1$ кратно 4, если $m$ кратно 4.
\end{itemize}

Конкретная реализация алгоритма может использовать в качестве выхода либо внутреннее состояние целиком (число $x_n$), либо его отдельные биты. Линейный конгруэнтный генератор является простым (то есть <<дешёвым>>) и быстрым генератором. Результат его работы -- статистически качественная псевдослучайная последовательность. Линейный конгруэнтный генератор нашёл широкое применение в качестве стандартной реализации функции для получения псевдослучайных чисел в различных компиляторах и библиотеках времени исполнения (см. таблицу~\ref{table:lcg}). Забегая вперёд, предупредим читателя, что его использование в криптографии недопустимо. Зная два последовательных значения выхода генератора ($x_n$ и $x_{n+1}$) и единственный параметр схемы $m$, можно решить систему уравнений и найти $a$ и $c$, чего будет достаточно для нахождения всей дальнейшей (или предыдущей) части последовательности. Параметр $m$, в свою очередь, можно найти перебором, начиная с некоторого $\min(X): X \geq x_i$, где $x_i$ -- наблюдаемые элементы последовательности.

\begin{landscape}
{\renewcommand{\arraystretch}{1.5}
\begin{table}[h]
\begin{tabular}{|p{0.34\linewidth}|r|r|r|l|}
\hline
									& a		& c		& m		& используемые биты	\\
\hline
\cite{Press:2007}~Numerical Recipes: The Art of Scientific Computing	& 1664525	& 1013904223	& $2^{32}$	& 			\\
\cite{Knuth:2005}~MMIX in The Art of Computer Programming & \tiny{6364136223846793005} & \tiny{1442695040888963407}	& $2^{64}$	&	\\
\hline
\cite{Entacher:1997}~ANSI C:
\tiny{(Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++)}		& 1103515245	& 12345		& $2^{31}$	& биты с 30 по 16-й	\\
\cite{Sirca:Horvat:2012}~glibc						& 1103515245	& 12345		& $2^{31}$	& биты с 30 по 0-й	\\
C99, C11 (ISO/IEC 9899) 						& 1103515245	& 12345		& $2^{32}$	& биты с 30 по 16-й	\\
C++11 (ISO/IEC 14882:2011) 						& 16807		& 0		& $2^{31} - 1$	& 			\\
Apple CarbonLib             			                       	& 16807		& 0		& $2^{31} - 1$	& 			\\
Microsoft Visual/Quick C/C++                                    	& 214013	& 2531011	& $2^{32}$	& биты с 30 по 16-й	\\
\hline
\cite{Bucknall:2001}~Borland Delphi					& 134775813	& 1		& $2^{32}$	& \\
\cite{MS-VBRAND:2004}~Microsoft Visual Basic \tiny{(версии 1--6)}	& 1140671485	& 12820163	& $2^{24}$	& 			\\
\cite{Mak:2003}~ Sun (Oracle) Java Runtime Environment			& 25214903917	& 11		& $2^{48} - 1$	& биты с 47 по 16-й	\\
\hline
\end{tabular}
\caption{Примеры параметров линейного конгруэнтного генератора в различных книгах, компиляторах и библиотеках времени исполнения\label{table:lcg}}
\end{table}
}
\end{landscape}