Loading [MathJax]/jax/output/HTML-CSS/jax.js
Now you are in the subtree of Lecture Notes public knowledge tree. 

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

Определение

Семейство функций 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)


Замечания

  1. Важна именно вычислительная неотличимость. Заменить ее на статистическую неотличимость не получится.
  2. Gn - сильно односторонняя функция.