We have seen that various important algorithms use random numbers (or, equivalently, independent random bits). But how do we get such bits?
One possible source is from outside the computer. We could obtain ``real'' random sequences, say, from radioactive decay. In most cases, however, this would not work: our computers are very fast and we have no physical device giving the equivalent of unbiased coin-tosses at this rate.
Thus we have to resort to generating our random bits by the computer. However, a long sequence generated by a short program is never random, according to the notion of randomness introduced using information complexity. We are still forced to use algorithms that generate random-looking sequences but, as Von Neumann (one of the first mathematicians to propose the use of these) put it, everybody using them is inevitably ``in the state of sin''. In this chapter, we will understand the kind of protection we can get against the graver consequences of this sin.
There are other reasons besides practical ones to study pseudorandom number generators. We often want to repeat some computation for various reasons, including error checking. In this case, if our source of random numbers was really random, then the only way to use the same random numbers again is to store them, using a lot of space. With pseudorandom numbers, this is not the case (or at least we only have to store the ``seed'', which is much shorter). Another, and more important, reason is that there are applications where what we want is only that the sequence should ``look random'' to somebody who does not know how it was generated. The collection of these applications is called cryptography, to be treated in a later chapter.
The way a pseudo-random bit generator works is that it turns a short random string called the ``seed'' into a longer pseudorandom string, in polynomial time. The resulting string has to ``look'' random. This latter can be defined exactly; roughly speaking, there should be no polynomial time algorithm that distinguishes it from a truly random sequence. Another feature, often easier to verify, is that no algorithm can predict any of its bits from the previous bits. We prove the equivalence of these two characterizations.
But how do we design such a generator? Various ad hoc methods that produce random-looking sequences (like taking the bits in the binary representation of a root of a given equation) turn out to produce strings that do not pass the strict criteria we impose. A general method to obtain such sequences is based on one-way functions: functions that are easy to evaluate but difficult to invert. While the existence of such functions is not proved (it would imply that P is different from NP), there are several candidates, that are secure at least against current techniques.