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 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 a pseudorandom generator if

{G_n}_{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 G_n can be replaced by the distribution of G(G(x))).

Often, 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.