Let G be a deterministic polynomial time function from N^{<?} to N^{<?} with stretch function In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ...
In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
 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. The word random is used to express lack of purpose, cause, order, or predictability in nonscientific parlance. ...
In mathematics, the uniform distributions are simple probability distributions. ...
Then we say G is a pseudorandom generator if  {G_{n}}_{n ? N}
is pseudorandom. A pseudorandom process is a process that appears random but is not. ...
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 oneway functions or hardcore predicates exist, then pseudorandom generators exist. It is also known that if Unsolved problems in computer science: Do oneway functions exist? A oneway function is a function that is easy to compute but hard to invert. ...
In cryptography, a hardcore predicate of a oneway function f(x) is a predicate b(x) which is easy to compute given x but is hard to compute given f(x). ...
 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 

Pseudorandom generators have numerous applications. In cryptography, a simple application is providing an efficient analog of `one time pads'. It is well known that in order to encrypt a message m in a way that the cipher text provides no information on the plaintext, the key k used should be random over strings of length m. Then m can be encrypted via . This operation is very costly in terms of key length. Key length can be reduced if we compromise on semantic security. Then, given G, which expands by a polynomial n^{c + 1}, then a sequence of n^{c} messages of length n can be encrypted by xoring each with the corresponding area of G(k) (inspired the idea of stream chipers). Pseudorandom generators may also be used to construct symmetric key cryptosystems, where any polynomial number of messages can be `safely' encrypted under the same key, that is, the polynomial n^{c} is not apriority known at time of key generation. Such a construction can be based on a generalization of pseudo random generators, called pseudorandom functions. A family of pseudorandom functions (PRF's) is a collection of efficiently computable keyed functions, which `act randomly' in the scene that no efficient algorithm can distinguish between an oracle to a function corresponding to a random key, and an oracle to a random function. It's known that if PRG's exist, than so do PRF's (for more details see pseudorandom function). One application of PRF's is in learning. Loosely speaking, given a sequence of examples e.t.c, the goal is to efficiently find a succinct representation of a function f out of a given class of functions consistent with the examples. PRF families (if exist) are a natural example of a class of functions with small representation size, but are not learnable. Semantic security is a widelyused definition for security in an asymmetric key encryption algorithm. ...
In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficientlycomputable functions which emulate a random oracle in the following way: No efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are...
In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficientlycomputable functions which emulate a random oracle in the following way: No efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are...
Another application is to derandomizing algorithms. A nice pseudorandom generator is a pseudorandom number generator, with  .
If a nice pseudorandom generator exists, then P=BPP. In fact, this strong derandomization result follows assuming the existence of a weaker type of pseudorandom generators, NisanWigderson type generator with exponential stretch. Their definition weakens the definition of PRG above in two essential ways. First, it allows G_{l} to run in exponential in n time. Another important difference is that the output distribution is only required to be indistinguishable from uniform for circuits of size S'(n) for some fixed exponential S' which is smaller than S, as opposed to generators as in the definition above. It's easy to see that the existence of nice pseudorandom generators of this kind for some polynomial S(n) is sufficient to imply P=BPP, and follows from plausible hardness assumptions (that some problems in EXP don't have sub exponential circuits). In a nutshell, the idea is to replace the randomness used by a BPP algorithm A, by G(s), where s is a short (O(log(n))) random string. By pseudorandomness of G, the behavior of A on any given x will not change much, so we can count the number of 1's output by A obtained iterating over the s, and answer according to the majority. That is, can be viewed as a non uniform distinguisher of proper size. For more details on this result and other derandomization results see BPP. In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
This article is about the complexity class. ...
In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ...
This article is about the complexity class. ...
Exp, in RolePlaying Games, stands for experience points. ...
This article is about the complexity class. ...
For more on these and other applications of PRG's, see chapters 10,17 in a draft of a book by Aurora and Barak available at http://www.cs.princeton.edu/theory/complexity/ This article incorporates material from pseudorandom generator on PlanetMath, which is licensed under the GFDL. PlanetMath is a free, collaborative, online mathematics encyclopedia. ...
