#### Определение

Семейство функций $G_n \colon \{0, 1\}^{k(n)} \rightarrow \{0, 1\}^{l(n)}$ называется **генератором псевдослучайных чисел**, если случайные величины $G_n(U_{k(n)})$ и $U_{l(n)}$ вычислительно неотличимы, то есть:
$$
\forall p(\cdot)\ \forall \{D_n\}\ \exists N\ \forall n > N\ |Pr\{D_n(\alpha_n) = 1\} - Pr\{D_n(\beta_n) = 1\}| < \frac{1}{p(n)}  
$$

***

#### Замечания

1.  Важна именно вычислительная неотличимость. Заменить ее на статистическую неотличимость не получится.
2.  $G_n$ - [сильно односторонняя функция](/nodes/248).