Now you are in the subtree of Lecture Notes public knowledge tree. 

Генератор псевдослучайных чисел

Определение

Семейство функций $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$ - сильно односторонняя функция.