Prime modulus multiplicative linear congruential generator

$y_{n+1}\equiv ay_{n}+b~~~(\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. [http://dx.doi.org/
5. [http://dx.doi.org/

1. [MC_1999_68_249]
2. [CPC_1997_103_0103]