Prime modulus multiplicative linear congruential generator

The prime modulus multiplicative linear congruential generator is a special type of linear congruential generator, given by:

$y_{n+1}\equiv ay_{n}+b\qquad ({\mathrm {mod} }~m),$

The parameter $m$ should be prime and as large as possible without causing a numerical overflow on the computer that it is running on. For example, for a 32-bit (31 bit + 1 sign bit) word size then the logical choice of $m$ is the Mersenne prime

$\left.m\right.=2^{31}-1=2147483647$,

with $a=7^{5}$ (a positive primitive root of $m$ see Ref.s 1 and 2), and $b=0$. With these parameters one is able to generate a series of $2.147\times 10^{9}$ pseudo-random numbers from one seed value. For an interesting discussion on how to choose an initial seed value see Ref. 3. For a list of other values of $m$ and $a$ see Ref.4 and for its use on 64-bit computers see Ref. 5.

References

1. D. W. Hutchinson, "A New Uniform Pesudorandom Number Generator", Communications of the ACM, 9 pp. 432-433 (1966)
2. P. A. W. Lewis and A. S. Goodman and J. M. Miller, "A pseudo-random number generator for the System/360", IBM Systems Journal 2 pp. 136 (1969)
3. G. Marsaglia, "Seeds for Random Number Generators",Communications of the ACM, 46 pp. 90-93 (2003)
4. Pierre L'Ecuyer, "Tables of linear congruential generators of different sizes and good lattice structure", Mathematics of Computation, 68 pp. 249 - 260 (1999)
5. Iosif G. Dyadkin and Kenneth G. Hamilton "A study of 64-bit multipliers for Lehmer pseudorandom number generators", Computer Physics Communications, 103 pp. 103-130 (1997)
6. Iosif G. Dyadkin and Kenneth G. Hamilton "A study of 128-bit multipliers for congruential pseudorandom number generators", Computer Physics Communications, 125 pp. 239-258 (2000)