49.2.1 Linear congruential generators

One of the most common PRNG is the linear congruential generator (LCG), which uses the recurrence:

N' = (a N + b) mod M      0 <= N', N < M

to generate a new integer number N' from an initial state N, a and b being known, fixed, recursion coefficients. The maximum number of integers the formula can produce is the modulus M.

To avoid certain non–random properties of a single linear congruential generator, several such generators with slightly different values of the multiplier coeffient are typically used in parallel, with a “master” generator that selects among them.

The most efficient LCGs have an M equal to a power of 2, most often 2^{32} or 2^{64}, because this allows the modulus operation to be computed by merely truncating all but the rightmost 32 or 64 bits¹¹.

LCGs should not be used for applications where high-quality randomness is critical. For example, they are not suitable for a Monte Carlo simulation or for cryptographic applications. A further problem of LCGs is that the lower–order bits of the generated sequence have a far shorter period than the sequence as a whole if M is set to a power of 2.