LehmerLCGs

Lehmer Linear Congruential Generators, often abbreviated as Lehmer LCGs, are a specific type of pseudorandom number generator. They are characterized by a particular choice of parameters in the standard linear congruential generator formula: X_{n+1} = (a X_n + c) mod m. The key feature of Lehmer LCGs is that the modulus m is a prime number, and the multiplier a is a primitive root modulo m.

This specific parameterization leads to generators with the maximum possible period length, which is m-1. The period is the number of distinct pseudorandom numbers generated before the sequence repeats. A full period is desirable for generating a long and seemingly random sequence.

The name "Lehmer" comes from Derrick Henry Lehmer, who was instrumental in their development and analysis. While providing excellent period lengths, Lehmer LCGs, like all LCGs, have known statistical weaknesses, particularly in higher dimensions. This means that sequences of numbers generated by Lehmer LCGs can exhibit patterns when analyzed in multiple dimensions, making them unsuitable for applications requiring high statistical quality, such as sophisticated Monte Carlo simulations or cryptography. However, for simpler applications where only a single sequence of numbers is needed, they can still be a computationally efficient option.