Pseudorandom generator
From Wikipedia, the free encyclopedia
Let G be a deterministic polynomial time function from N<ω to N<ω with stretch function
- l:N → N,
so that if x has length n then G(x) has length l(n). Then let Gn 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 a pseudorandom generator if
- {Gn}n ∈ 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 Gn can be replaced by the distribution of G(G(x))).
Oftentimes, we are concerned not with the behavior of G on all strings, but only on strings of some prescribed length. This case allows a slightly easier definition:
A function 
with 
is a pseudorandom generator if
can be computed in 
time, and
is pseudorandom.
It is an open problem whether or not pseudorandom generators exist. It is known that if one-way functions or hard-core predicates exist, then pseudorandom generators exist. It is also known that if
- l(n) > n,
there is some other pseudorandom generator with
- l(n) > p(n)
for any polynomial, p(n). This follows from the following theorem:
Theorem: If there is a pseudorandom generator
then for any 
, there is a pseudorandom generator
A nice pseudorandom generator is a pseudorandom number generator,
with
.
If a nice pseudorandom generator exists, then P=BPP.
This article incorporates material from pseudorandom generator on PlanetMath, which is licensed under the GFDL.
