Linear Congruential Generator

• Benefits:
  • Constants can be chosen such that they emit every possible output value once before repeating
• Problems:
  • The high bits of the state do not affect the low bits at all

Algorithm

$$\begin{array}{llc}m& \text{the modulus}& m>0\\ a& \text{the multiplier}& 0<a<m\\ c& \text{the increment}& 0\le c<m\\ X_0& \text{the starting value, or seed}& 0\le X_0<m\end{array}$$

$X_{n+1}=(a{X}_n+c)\mathrm{mod}m$

Links

• Linear congruential generator - Wikipedia
• Random number generators: good ones are hard to find | Communications of the ACM