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))$ ).
随便看	ExampleOfFalseImpliesTrue example of false implies true ExampleOfFermatsLastTheorem example of Fermat’s last theorem ExampleOfFibreProduct example of fibre product ExampleOfFourExponentialsConjecture example of four exponentials conjecture ExampleOfFourierSeries example of Fourier series ExampleOfFreeModule example of free module ExampleOfFreeModuleWithBasesOfDiffrentCardinality example of free module with bases of diffrent cardinality ExampleOfFullyInvariantSubgroup example of fully invariant subgroup ExampleOfFunctionNotLebesgueMeasurableWithMeasurableLevelSets example of function not Lebesgue Measurable with measurable level sets ExampleOfFunctorOfPointsOfAScheme example of functor of points of a scheme ExampleOfFundamentalTheoremOfDemography example of fundamental theorem of demography ExampleOfGcd example of gcd ExampleOfGodelNumbering