Many programs (e. g., simulations, one-time-pads) make use of numbers that are supposed to be random. A genuine source of randomness might be a subroutine that made calls on something like a built-in Geiger counter. We will be concerned with algorithms that produce a sequence of numbers (usually 0's and 1's) which appears random (precise definition will be given later).
A typical example of such an algorithm is the function rand() in the C programming language. Each call updates an internally maintained using the formula
I recently wrote a program to roll dice which involved using rand() mod 6. In over 100 calls, it never happened that the same number occurred on two consecutive rolls, even though this should have happened about times! This suggests this particular generator has some problems.13
In this section, we will present random number generators for which it can be proved (given assumptions like (QRA)) that such problems will not occur.