Изменения
→Определение
== Определение ==
Функция <tex> g: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''непредсказуемой'', если если <tex> \forall A </tex>, удовл. удовлетворяющего классу [[Сложностный класс BPP|BPP]] , вероятность <tex> P(A(y_{1},...,y_{i-1},1^n) = y_{i} \wedge y = g(x)) \le 1/2 + \epsilon(n) </tex>, где по всем <tex> x \in \{0,1\}^n </tex>, а где функция <tex> \epsilon(n) </tex> -- пренебрежимо мала.
== Теорема ==
Функция <tex> g </tex> является случайным генератором тогда и только тогда, когда <tex> g </tex> - непредсказуемая.
===== Без доказательства. =====
