Pseudorandom generator

In theoretical computer science and cryptography, a pseudorandom generator, or PRG, is a deterministic procedure that expands a short random seed into a longer string that looks random, in the sense that no statistical test drawn from an allowed class of tests can reliably distinguish the output from a string chosen uniformly at random. If the seed has length l and the output has length n, with l less than n, the difference n minus l is called the stretch of the generator. Pseudorandom generators occupy a central place in computational complexity theory: proving that cryptographically secure pseudorandom generators exist would show that P is not equal to NP, one of the most important open problems in the field, and researchers have shown that pseudorandom generators can be constructed from any one way function, linking cryptographic hardness assumptions directly to derandomization. Influential constructions were proposed by Noam Nisan and Avi Wigderson in 1991, and later work produced specialized generators tailored to restricted computational models such as logarithmic space machines and low degree polynomial functions. Despite decades of study and widespread belief that they exist, cryptographically secure pseudorandom generators remain unproven, reflecting deep unresolved questions in computational complexity theory.