Linear Congruential Generator

Linear congruential generator is very basic algorithm to generate random numbers. Although it is a very fast algorithm, it may not generate very random variables. The formula of that generator is given below.

Xn + 1 = (Xn x A) + B(mod M)

Despite the basicness of this formula, the algorithm has some properties. Firstly, B and M are relatively prime. Secondly, A-1 should be divisible by all prime factors of M. Finally, A-1 should be a multiple of 4. For example:

A = 4, B = 3, M = 8
  1. B & M are relatively prime. Thus, it suffices the first condition.
  2. A - 1 = 3 It is not divisible by prime factors of M. Therefore, it violates the second rule.
  3. A - 1 = 3 It is not multiple of 4. Therefore, it violates the second rule.

Therefore, it cannot generate any random number.

You can understand how this algorithm works by returning to the initial value after all generation of some random numbers.

For more details see the Wikipedia page for Linear congruential generator.

Contributed by Mert Deniz Güngör