$X\_\{k+1\}\; =\; X\_kcdot\; g~~bmod~~n$

where n is a prime number or a power of a prime number, g is an element of high multiplicative order modulo n (e.g., a primitive root modulo n), and $X\_0$ is co-prime to $n$.

Parameters in common use

Park and Miller suggested particular values $n=2^\{31\}-1=2147483647$ (a Mersenne prime $M\_\{31\}$) and $g=16807$ (a primitive root modulo $M\_\{31\}$). The Park–Miller RNG with these parameters (known as "MINSTD") is a build-in RNG in Apple CarbonLib. ZX Spectrum uses the Park–Miller RNG with parameters $n=2^\{16\}+1=65537$ (a Fermat prime $F\_4$) and g=75 (a primitive root modulo $F\_4$). The CRAY random number generator RANF uses a Park–Miller RNG with $n=2^\{48\}$ and $g=44485709377909$. Another popular pair of parameters is $n\; =\; 2^\{32\}-5\; =4294967291$ and $g=279470273$.

The GNU Scientific Library includes several random number generators of the Park-Miller form, including Park-Miller random number generator "MINSTD", the CRAY random number generator "RANF", and the infamous IBM random number generator "RANDU".

Relation to LCG

While the Park–Miller RNG can be viewed as a particular case of the linear congruential generator with $c=0$, it is a special case that implies certain restrictions and properties. In particular, for the Park–Miller RNG, the initial seed $X\_0$ must be co-prime to the modulus n that is not required for LCGs in general. The choice of the modulus n and the multiplier g is also more restrictive for the Park–Miller RNG. In difference from LCG, the maximum period of the Park–Miller RNG equals n-1 and it is such when n is prime and g is a primitive root modulo n.

On the other hand, the discrete logarithms (to base g or any primitive root modulo n) of $X\_k$ in $mathbb\{Z\}\_n$ represent linear congruential sequence modulo Euler totient $phi(n)$.

Sample C99 code

Using C99 code, this is written as follows:

include 

uint32_t lcg_rand (uint32_t a)
{
   return ((uint64_t)a * 279470273) % 4294967291;
}

References

• W.H. Payne, J.R. Rabung, T.P. Bogyo (1969). "Coding the Lehmer pseudo-random number generator". Communications of the ACM 12 (2): 85–86. (alternative link to PDF)
• S.K. Park and K.W. Miller (1988). "Random Number Generators: Good Ones Are Hard To Find". Communications of the ACM 31 (10): 1192–1201. (alternative link to PDF)
• Steve Park Random Number Generators
• Park-Miller-Carta Pseudo-Random Number Generator