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:
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)
“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 animals—just 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)
“One definition of man is “an intelligence served by organs.””
—Ralph Waldo Emerson (1803–1882)