pseudorandom generator

Let $G$ be a deterministic polynomial-time function from $\\mathbb{N}^{<\\omega}$ to $\\mathbb{N}^{<\\omega}$ with stretch function $l:\\mathbb{N}\\rightarrow\\mathbb{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 pseudorandom generator if $\\{G_{n}\\}_{n\\in\\mathbb{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))$ ).

单词	PseudorandomGenerator
释义	pseudorandom generator Let $G$ be a deterministic polynomial-time function from $\\mathbb{N}^{<\\omega}$ to $\\mathbb{N}^{<\\omega}$ with stretch function $l:\\mathbb{N}\\rightarrow\\mathbb{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 pseudorandom generator if $\\{G_{n}\\}_{n\\in\\mathbb{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))$ ).
随便看	alternative definition of a multigraph AlternativeDefinitionOfAQuasigroup alternative definition of a quasigroup AlternativeDefinitionOfCardinality alternative definition of cardinality AlternativeDefinitionOfGroup alternative definition of group AlternativeDefinitionOfKrullValuation alternative definition of Krull valuation AlternativeDefinitionOfLebesgueIntegralAn alternative definition of Lebesgue integral, an AlternativeDefinitionOfMetricSpace alternative definition of metric space AlternativeDefinitionOfTheNaturalLogarithm alternative definition of the natural logarithm AlternativeDefinitionOfValuation alternative definition of valuation AlternativeDefinitionsOfCountable alternative definitions of countable AlternativeProofOfConditionOnANearRingToBeARing alternative proof of condition on a near ring to be a ring AlternativeProofOfDerivativeOfXn alternative proof of derivative of x^n AlternativeProofOfEuclidsLemma alternative proof of Euclid’s lemma