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
Famous quotes containing the word definition:
“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)
“No man, not even a doctor, ever gives any other definition of what a nurse should be than thisdevoted and obedient. This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (18201910)
“According to our social pyramid, all men who feel displaced racially, culturally, and/or because of economic hardships will turn on those whom they feel they can order and humiliate, usually women, children, and animalsjust as they have been ordered and humiliated by those privileged few who are in power. However, this definition does not explain why there are privileged men who behave this way toward women.”
—Ana Castillo (b. 1953)