伪随机数发生器

$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)$$