伪随机性

• 扩张性
• 伪随机性：

$$|Pr[D(U_{l(n)})=1]-Pr[D(f)]|$$

todo

引入伪随机数是因为真随机数生成代价太高，希望用一个短的真随机生成一个相当长的伪随机序列

因为值域只能覆盖一部分，所以可以构建一个表来暴力破解，但这个不是 PPT 时间了

PRG 的输出和均匀一致相去甚远

PRG 的存在当且仅当单项函数存在

伪随机函数