pseudorandom generator

Let G be a deterministicMathworldPlanetmath polynomial-time functionMathworldPlanetmath from <ω to <ω with stretch function l:, so that if x has length n then G(x) has length l(n). Then let Gn be the distributionDlmfPlanetmathPlanetmath on strings of length l(n) defined by the output of G on a randomly selected string of length n selected by the uniform distributionMathworldPlanetmath.

Then we say G is pseudorandom generator if {Gn}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 Gn can be replaced by the distribution of G(G(x))).

Title pseudorandom generator
Canonical name PseudorandomGenerator
Date of creation 2013-03-22 13:03:16
Last modified on 2013-03-22 13:03:16
Owner Henry (455)
Last modified by Henry (455)
Numerical id 6
Author Henry (455)
Entry type Definition
Classification msc 68Q30
Defines stretch function