The Lehmer random number generator (named after D. H. Lehmer), sometimes also referred to as the Park–Miller random number generator (after Stephen K. Park and Keith W. Miller), is a variant of linear congruential generator
Linear congruential generator
A Linear Congruential Generator represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast....
In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it...
. A general formula of a random number generator (RNG) of this type is:
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
or a power of a prime number, the multiplier g is an element of high multiplicative order
Multiplicative order
In number theory, given an integer a and a positive integer n with gcd = 1, the multiplicative order of a modulo n is the smallest positive integer k withThe order of a modulo n is usually written ordn, or On.- Example :To determine the multiplicative order of 4 modulo 7, we compute 42 = 16 ≡ 2 ...
In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g modulo n. In other words, g is a generator of the multiplicative group of integers modulo n...
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
to n.
Parameters in common use
In 1988, Park and Miller suggested a Lehmer RNG with particular parameters n = 2 − 1 = 2,147,483,647 (a Mersenne prime
Mersenne prime
In mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...
M) and g = 7 = 16,807 (a primitive root modulo M), now known as MINSTD. Although MINSTD was later criticized by Marsaglia and Sullivan, it is still in use today (in particular, in CarbonLib).
The ZX Spectrum is an 8-bit personal home computer released in the United Kingdom in 1982 by Sinclair Research Ltd...
uses the Lehmer RNG with parameters n = 2 + 1 = 65,537 (a Fermat prime F) and g = 75 (a primitive root modulo F). The CRAY
Cray
Cray Inc. is an American supercomputer manufacturer based in Seattle, Washington. The company's predecessor, Cray Research, Inc. , was founded in 1972 by computer designer Seymour Cray. Seymour Cray went on to form the spin-off Cray Computer Corporation , in 1989, which went bankrupt in 1995,...
random number generator RANF is a Lehmer RNG with n = 2 and g = 44,485,709,377,909. Another popular pair of parameters is n = 2 − 5 = 4,294,967,291 and g = 279,470,273.
LC53 in Forth (programming language) uses parameters n = 232 − 5 = 4,294,967,291 and g = 232 − 333333333 = 3,961,633,963.
In computing, the GNU Scientific Library is a software library written in the C programming language for numerical calculations in applied mathematics and science...
includes several random number generators of the Lehmer form, including MINSTD, RANF, and the infamous IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
A Linear Congruential Generator represents one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast....
with , it is a special case that implies certain restrictions and properties. In particular, for the Lehmer RNG, the initial seed X must be coprime
Coprime
In number theory, a branch of mathematics, two integers a and b are said to be coprime or relatively prime if the only positive integer that evenly divides both of them is 1. This is the same thing as their greatest common divisor being 1...
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 Lehmer RNG. In contrast to LCG, the maximum period of the Lehmer RNG equals n−1 and it is such when n is prime and g is a primitive root modulo n.
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
s (to base g or any primitive root modulo n) of X in represent linear congruential sequence modulo Euler totient .
Sample C99 code
Using C code, the Lehmer generator using the "popular pair" of parameters mentioned above can be written as follows:
represent linear congruential sequence modulo Euler totient 
.