伪随机

伪随机性：如果一个分布中抽取的样本不能有效地和均匀随机选取的样本区分开，那么这个分布就是伪随机分布

伪随机数发生器

$l$ 是多项式，$G$ 是多项式时间算法，能够做到 $G:\{0,1{\}}^n\to \{0,1{\}}^{l(n)}$

G 是 伪随机数发生器（PRG），必须满足：

• 扩张性：$\forall n:l(n)>n$
• 伪随机性：$\{G(U_n)\}$ 是伪随机分布序列，对于任意 PPT 区分算法 D（输出 1 则是认为来自真随机，输出 0 则是来自伪随机）

$$|Pr[D(U_{l(n)})=1]-Pr[D(G(U_n)=1)=1]|=negl(n)$$指向原始笔记的链接

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

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

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

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