In the following we shall consider methods for generating a sequence of random real numbers U_n, uniformly distributed between zero and one. In other words, every number in the sequence is in [0,1) and the chance of being any number of [0,1) is equal. Since a computer can represent a real number with only finite accuracy, we shall actually be generating integers X_n between zero and some number m; the fraction

U_n = X_n/m

will then lie between zero and one.

One of the most successful random number generators known today are special cases of the following scheme, which is called the linear congruential method. We choose four "magic numbers":

The desired sequence of random numbers < X_n > is then obtained by setting

This is called a linear congruential sequence.

For example, the sequence obtained when X₀ = a = c = 7, m = 10, is

7, 6, 9, 0, 7, 6, 9, 0, ...

As this example shows, the sequence is not always "random" for all choices of X₀, a, c, and m; the way of choosing these values appropriately is the most important part of this method.

Because X_n+1 is determined by X_n, so once some number in the sequence get repeated, the sequence will get into a cycle. And because there are only m possible different values for X_n's, so the sequence will get into a cycle in at most m steps and the period is at most of length m.

It's very reasonable that we want the sequence to have long period so it might look random. So m is chosen to be very big, e.g. 2³¹.

The special case c = 0 deserves explicit mention, since the number generation process is a little faster in this case. Lehmer's original generation method had c = 0, although he mentioned c ≠ 0 as a possibility. The terms multiplicative congruential method and mixed congruential method are used by many authors to denote linear congruential methods with c = 0 and c ≠ 0.

In the case of multiplicative congruential method, it's easy to see X_n = 0 should not be allowed, otherwise the sequence will be 0 forever afterwards. So the period is at most m-1. We can express X_n as aⁿX₀ . Notice that X₀ ≠ 0, so period of the sequence is the smallest positive value of k for which

The Euler-Fermat Theorem states that if a and m are relatively prime, then a^φ(m) = 1 mod m, where φ(m) is the Euler's totient function,meaning the number of positive integers less than or equal to n that are coprime to n. The period, therefore, can be no greater than φ(m). For a given value of m, we seek a such that k in equation (3.1) is φ(m). Such a number a is called a primitive root modulo m .(See [3], or other texts on number theory for general discussions of primitive roots)

For example, consider m = 31 and a = 7, 7¹⁵ =1 mod 31, but φ(31) = 30, so 7 is not a primitive root modulo 31. If we consider a = 3, we will find it's a primitive root modulo 31, so the sequence will have period 30.

It turns out that m has a pimitive root if and only if m is equal to 1, 2, 4 or of the form 2^αp^β, where p is an odd prime, α = 0 or 1, and β ≥ 1.

For general m, the period may not be as big as φ(m), but by choosing a properly, period that is big enough for use can still be achieved.

An an example of this kind of generator being used is in program RANDU, which for many years was the most widely used random number generator in the world. (Page 18-20 of [4])

The generator in RANDU is essentially (but not exactly the same as)

X_n+1 =65539X_n mod 2³¹.

RANDU is still available at a number of computer centers and is used in some statistical analysis and simulation packages.

The case of mixed congruential method, i.e. c ≠ 0, is much more complicated. There is a powerful theorem as follows:

The proof of the theorem is left out here and can be found in Page 15-18 of [1].