Генератор псевдослучайных чисел
Определение
Семейство функций Gn:{0,1}k(n)→{0,1}l(n) называется генератором псевдослучайных чисел, если случайные величины Gn(Uk(n)) и Ul(n) вычислительно неотличимы, то есть:
∀p(⋅) ∀{Dn} ∃N ∀n>N |Pr{Dn(αn)=1}−Pr{Dn(βn)=1}|<1p(n)
Замечания
- Важна именно вычислительная неотличимость. Заменить ее на статистическую неотличимость не получится.
- Gn - сильно односторонняя функция.