Изменения
Нет описания правки
== Определения ==
Если существуют односторонние функции, то <tex> \forall c ~\exists \langle E,D \rangle</tex> -- вычислительно безопасная схема: <tex> |k| = n, |x| = n^c </tex>
===== Без доказательства =====
= Псевдослучайные генераторы =
== Определение ==
Слово <tex> x: |x| = n </tex> называется ''с - случайным'', если его нельзя вывести программой на языке Pascal длиной не более <tex> cn </tex>, где <tex> 0 < c < 1 </tex>.
== Определение ==
Функция <tex> g: \{0,1\}^n \to \{0,1\}^m, m > n </tex> называется ''псевдослучайным генератором'', если <tex> \forall A </tex>, удовл. классу [[Сложностный класс BPP|BPP]] разность вероятностей <tex> |P(A(g(x)) = 1) - P(A(y) = 1)| </tex> -- пренебрежимо мала. Здесь <tex> x \in \{0,1\}^n, y \in \{0,1\}^m </tex>.
== Теорема ==
Если существуют односторонние функции, то существуют псевдослучайные генераторы.
===== Без доказательства. =====
== Определение ==
Функция <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> - непредсказуемая.
===== Без доказательства. =====
