|
|
|
|
pseudorandom generator
|
(Definition)
|
|
|
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))$ ).
|
"pseudorandom generator" is owned by Henry.
|
|
(view preamble | get metadata)
| Also defines: |
stretch function |
|
|
Cross-references: multiple, sequence, expands, translates, pseudorandom, uniform distribution, strings, distribution, length, function, polynomial-time, deterministic
There is 1 reference to this entry.
This is version 3 of pseudorandom generator, born on 2002-09-15, modified 2005-02-14.
Object id is 3460, canonical name is PsuedorandomGenerator.
Accessed 3673 times total.
Classification:
| AMS MSC: | 68Q30 (Computer science :: Theory of computing :: Algorithmic information theory ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|