Pseudorandom Generator - Definition


Let Fn = {f: {0, 1}n → T} be a class of functions. A function G: {0, 1}s → {0, 1}n, where s < n, is a pseudorandom generator against Fn with bias ε if for every f in Fn, the statistical distance between the distributions f(G(X)), where X is sampled from the uniform distribution on {0, 1}s, and f(Y), where Y is sampled from the uniform distribution on {0, 1}n, is at most ε.

The quantity s is called the seed length and the quantity n - s is called the stretch of the pseudorandom generator. Functions from the class Fn are sometimes called adversaries.

A pseudorandom generator against a family of adversaries F = {Fn} with bias ε(n) is a collection of pseudorandom generators {Gn: {0, 1}s(n) → {0, 1}n}, where Gn is a pseudorandom generator against Fn with bias ε(n).

In most applications, the family F represents some model of computation, and one is interested in desigining a pseudorandom generator that is computable in the same or some closely related model.

Read more about this topic:  Pseudorandom Generator

Other articles related to "definition, definitions":

Sustainable Development - Definition
... which included what is now one of the most widely recognised definitions "Sustainable development is development that meets the needs of the present without compromising the ability of future ... It offers an integrated vision and definition of strong sustainability ... It generates a more nuanced definition of sustainable development “the need to ensure a better quality of life for all, now and into the future, in a just and ...
Definition - In Medicine
... In medical dictionaries, definitions should to the greatest extent possible be simple and easy to understand, preferably even by the general public useful clinically or in related areas where the ...
Pashtun People - Pashtuns Defined
... These three definitions may be described as the ethno-linguistic definition, the religious-cultural definition, and the patrilineal definition, respectively ...
Definition of Dietary Fiber
... fiber was defined to be the components of plants that resist human digestive enzymes, a definition that includes lignin and polysaccharides ... The definition was later changed to also include resistant starches, along with inulin and other oligosaccharides ... Official definition of dietary fiber differs a little among different institutions Organization (reference) Definition Institute of Medicine Dietary fiber consists of nondigestible carbohydrates and lignin that are ...
ESPN - High Definition
... ESPN launched its 720p high-definition simulcast, originally branded as ESPNHD, on March 20, 2001 ... Live studio shows, along with most live events on ESPN, use high definition ... Footage from non-HD sources is presented in a standard definition, 43 format with stylized pillarboxes ...

Famous quotes containing the word definition:

    Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.
    Elaine Heffner (20th century)

    The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.
    Jean Baudrillard (b. 1929)

    ... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.
    George Eliot [Mary Ann (or Marian)