What is a pseudo random number generator?

A pseudo random number generator (PRG) is an ''efficient'' deterministic algorithm that takes a ''short'' truly random string and produces a ''longer'' output that ''looks'' completely random. As truly random we consider such things as radioactive decay, tossing a fair coin etc.

We can intuitively see this as a machine, A, that tries to decide what position the switch in the figure below is in. He only knows that with probability 1/2 the switch is "up" and with probability 1/2 it is "down".

For those who have studied some complexity theory, we can be a little more specific:
By ''efficient'' we mean that the time needed to compute the pseudo random output is polynomial in the length of the input seed.
By ''short'' and ''longer'' we require that the length of the output is strictly longer than the seed. It can be shown that this is sufficient to actually get any polynomial stretching factor.
By ''looks'' random we mean that no probabilistic polynomial time algorithm exists that can decide (with probability significantly greater than 1/2) if a given sample is from the generator or is a truly random string of the same length.

An example:

Which of these sequences do you think is random and which is not? One has been produced by a series of coin flips (and ought to be random) whereas the other has been produced by taking a prime number, p, computing 1/p and extracting a set of consecutive decimals in this expansion.

Click here to see the answer

References:

Goldreich & Levin: "A Hard-Core Predicate for any One-way Function". Proceedings FOCS 1988.
Goldreich et al: "How to Construct Random Function". J. of ACM no 4 1986.
Goldreich et al: "On the existence of Pseudo Random Generators". Proceedings FOCS 1988.
Håstad et al: "Construction of a pseudo-random generator from any one-way function". Proceedings STOC 1989, 1990.
Yao: "Theory and Applications of Trapdoor Functions". Proceedings FOCS 1982.

Good introductions to the theoretical aspects of cryptography are found in:

Diffie & Hellman: "New Directions in Cryptography". IEEE Trans. on Info. Theory 6 1976.
Goldreich: "Foundations of Cryptography". Lecture notes. Computer Science dept. of Technion, Haifa 1989.

Mats Näslund <matsn@nada.kth.se>, September 1994