Linear Congruential Generators (LCGs) are a popular method for generating pseudo-random numbers. They owe their simplicity to a straightforward formula:

$$X\_{n+1} = (A \cdot X\_n + C) \mod M$$

where: • $X_{n+1}$ is the next random number. • $X_n$ is the current random number. • $A$, $C$, and $M$ are non-negative integer constants. • $M$ is the modulus. • $0 \leq X_n < M$.

To ensure that an LCG behaves as desired, particularly that it produces numbers with a long period and good statistical properties, choosing appropriate values for $A$, $C$, and $M$ is crucial.

Selecting the Modulus (M)

1. Bit Length: Choose $M$ as a power of 2 or a large prime number. A common choice is $M = 2^\{31\}$ or $M = 2^\{32\}$ due to hardware efficiency.
2. Periodicity: The maximum period of an LCG is $M$ when $A$, $C$, and $M$ are selected properly.

Selecting the Multiplier (A)

1. Full Period Criterion: For full period LCGs, a common criterion is that: • $A \equiv 1 \pmod{p}$ for every prime $p$ dividing $M$. • $A \equiv 1 \pmod\{4\}$ if $M$ is a multiple of 4.
2. Simple Choices: Use an increment based on the formula $A = 4n + 1$ when $M$ is a power of 2. However, test empirically for randomness.

Example

If $M = 16$, a suitable multiplier can be $A = 5$ which satisfies $A \equiv 1 \pmod{4}$.

Selecting the Increment (C)

1. Co-prime Criteria: $C$ should be co-prime to $M$. This ensures the maximum period when the other conditions are met.
2. Avoid Zero: When $A \equiv 1 \pmod{M}$, choose non-zero $C$ to avoid sequential repetition.

Example

For $M = 16$ and $A = 5$, a possible increment is $C = 3$. Since 3 is co-prime to 16 (common factors are only 1), it is valid.

Table of Key Points

Further Considerations

• Seed Selection ($X_0$): The seed must be chosen carefully to prevent predictable sequences. It is not bound by the co-prime rule. • Empirical Testing: Once parameters are chosen, empirical testing is essential to evaluate randomness quality using tests like the chi-square or Kolmogorov-Smirnov tests. • Modern Practices: Despite their historical popularity, LCGs are typically replaced in modern applications by more complex, cryptographically secure generators for applications requiring high-quality randomness.

In summary, the correct choice of $A$, $C$, and $M$ is crucial for the LCG to function effectively. While LCGs have limitations, when configured correctly, they serve well for applications requiring consistent and reproducible pseudo-random numbers.