Pseudo-random number generators

[This section is based on Blum, Blum, & Shub, ``A simple unpredictable pseudo-random number generator,'' SIAM J. Computing 15, 364-383.]

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 $N$ using the formula

$$N=N*1103515245+12345\quad\hbox{mod } 4294967296=2^{32}$$

with the output given by $2^{-16}N$ mod $2^{15}$.

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 $1/6(100)$ times! This suggests this particular generator has some problems.¹³

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.

Footnotes

... problems.¹³

Knuth suggests that a better way to obtain a random number between 0 and $k-1$ is to use $k$rand()${}/M$, where $M$ is the maximum value of rand().