Linear congruential generator

FCC link

The linear congruential generator is a very simple example of a random number generator. All linear congruential generators use this formula:

$r_{n + 1} = (a \times r_n + c) \bmod m$

Where:

• $ r_0 $ is a seed.
• $r_1$, $r_2$, $r_3$, ..., are the random numbers.
• $a$, $c$, $m$ are constants.

If one chooses the values of $a$, $c$ and $m$ with care, then the generator produces a uniform distribution of integers from $0$ to $m - 1$.

LCG numbers have poor quality. $r_n$ and $r_{n + 1}$ are not independent, as true random numbers would be. Anyone who knows $r_n$ can predict $r_{n + 1}$, therefore LCG is not cryptographically secure. The LCG is still good enough for simple tasks like Miller-Rabin primality test, or FreeCell deals. Among the benefits of the LCG, one can easily reproduce a sequence of numbers, from the same $r_0$. One can also reproduce such sequence with a different programming language, because the formula is so simple.