pseudorandom generator

Let $G$ be a deterministic polynomial-time function from $\mathbb{N}^{<\omega}$ to $\mathbb{N}^{<\omega}$ with stretch function $l:\mathbb{N}\rightarrow\mathbb{N}$, so that if $x$ has length $n$ then $G(x)$ has length $l(n)$. Then let $G_{n}$ be the distribution on strings of length $l(n)$ defined by the output of $G$ on a randomly selected string of length $n$ selected by the uniform distribution.

Then we say $G$ is pseudorandom generator if $\{G_{n}\}_{n\in\mathbb{N}}$ is pseudorandom.

In effect, $G$ translates a random input of length $n$ to a pseudorandom output of length $l(n)$. Assuming $l(n)>n$, this expands a random sequence (and can be applied multiple times, since $G_{n}$ can be replaced by the distribution of $G(G(x))$).

Title pseudorandom generator PseudorandomGenerator 2013-03-22 13:03:16 2013-03-22 13:03:16 Henry (455) Henry (455) 6 Henry (455) Definition msc 68Q30 stretch function