Генератор псевдослучайных чисел
Определение
Семейство функций $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)}
$$
Замечания
- Важна именно вычислительная неотличимость. Заменить ее на статистическую неотличимость не получится.
- $G_n$ - сильно односторонняя функция.