Selecting the right random number generator (RNG) is crucial for many applications in statistics, cryptography, numerical simulations, gaming, and more. With different algorithms having distinct properties, there is no single “best” RNG. The optimal choice depends on weighing factors like speed, randomness quality, repeatability, and implementation difficulty for your specific requirements.
What is a random number generator?
A random number generator is an algorithm that produces a sequence of numbers that appears statistically random. The output sequence is completely determined by an initial value called a seed. For a given seed, the RNG will always produce the same sequence. This determinism contrasts with physically-based processes like radioactive decay which are intrinsically random.
Pseudorandom number generators (PRNGs) use mathematical formulas and deterministic logic to emulate randomness. While the output sequences pass many statistical tests of randomness, PRNGs are not truly random since the results are predictable given knowledge of the algorithm and seed. Cryptographically secure PRNGs (CSPRNGs) are a subclass designed to provide security for applications like cryptography.
Properties of random number generators
Key properties to evaluate in RNGs include:
- Randomness quality – Passing statistical tests for randomness. Long periodicity before patterns repeat.
- Unpredictability – Inability to predict future values even with knowledge of previous outputs.
- Uniformity – Flat distribution over the intended range.
- Efficiency – Speed and computational resource requirements.
- Reproducibility – Ability to reproduce sequences by reusing seeds.
- Portability – Ability to implement across platforms and languages.
There are inherent tradeoffs between properties – an RNG may excel in some areas but compromise in others. Cryptographic security also often competes with performance and reproducibility.
Types of random number generators
There are several categories of random number generator algorithms:
Linear congruential generators (LCGs)
LCGs are one of the oldest and most basic PRNGs. The output sequence is defined by a recurrence relation:
Xn+1 = (aXn + c) mod m
Where X is the sequence, n is the index, a is the multiplier, c is the increment, and m is the modulus. For proper choices of a, c, and m, LCGs can produce full-period sequences without repeating. However, lower order bits have shorter periodicity, and the sequences fail some statistical randomness tests.
Advantages of LCGs include very fast speed and ease of implementation. They are commonly available in software libraries.
Lagged Fibonacci generators
This class obtains each new value by combining two previous values with binary arithmetic operations like addition, subtraction, multiplication, or XOR. For example:
Xn = (Xn-100 + Xn-373) mod m
The lag parameters provide better randomness but increase state storage requirements. These PRNGs perform well statistically but have quantifiable defects making them inappropriate for cryptography.
Cryptographically secure pseudorandom number generators (CSPRNG)
CSPRNGs are designed to provide security for cryptographic applications. They use entropy inputs and cryptographic functions to produce output sequences that are computationally indistinguishable from true randomness. CSPRNGs should resist prediction even if attackers have full knowledge of the algorithm and previously generated values.
Common examples include:
- Blum Blum Shub – Based on the factorization difficulty of large primes.
- Cryptographic hash functions like SHA-1, SHA-2.
- Block ciphers like AES in counter mode.
A downside is significantly lower performance than non-cryptographic PRNGs.
True random number generators (TRNG)
TRNGs extract randomness from unpredictable physical processes like radioactive decay, thermal noise, shot noise, clock drift, or atmospheric turbulence. Sources of entropy need to be carefully selected and processed to filter bias and compensate for low bit rates.
TRNGs produce true randomness but can have slow speeds and lack of reproducibility. Hybrid designs combine TRNG entropy sources with CSPRNGs to improve speed and enable saveable seeds.
Quasirandom number generators
QRNGs use deterministic algorithms to produce low-discrepancy sequences that appear highly uniform. They aim to cover the output space efficiently rather than emulate randomness. Popular examples include Sobol, Niederreiter, and Halton sequences.
Their advantages are very high dimensional uniformity and reproducibility using small seeds. Disadvantages include recognizable patterns and failing most randomness tests. QRNGs are mainly used for numerical simulations requiring even coverage.
Statistical testing
Statistical tests are indispensable for quantifying the randomness quality and patterns present in RNG outputs. Common test suites include:
Diehard tests
This venerable battery of tests probes randomness weaknesses through assessments like birthdays, overlapping permutations, binary rank tests, counts-the-ones, parking lot, and monkey tests. Roughly quantifies the confidence range of observed deviations from perfect randomness.
TestU01 suite
Developed by L’Ecuyer and Simard at the University of Montreal, TestU01 provides an extensive, robust set of empirical statistical tests for RNGs. Capable of detecting a wide range of flaws. Implemented in ANSI C.
NIST statistical test suite
A widely used standard battery of statistical tests developed by the National Institute of Standards and Technology (NIST). Focuses on cryptographic applications. Python and C++ implementations are available.
Passing all tests provides evidence of statistical quality but does not guarantee suitability or randomness for all purposes. Detailed understanding of test internals, weaknesses, dependencies and false positives/negatives rates is needed for proper interpretation.
Comparing specific random number generators
We can now examine some widely-used RNG options in greater detail:
Linear congruential generators
| LCG Algorithm | Features | Usage Guidance |
|---|---|---|
| Minstd_rand |
|
Reasonable general-purpose LCG. Not for cryptography. |
| gcc’s rand() |
|
Suitable for recreational programs but avoid for simulations or security. |
| Multplicative LCG |
|
Decent general-purpose LCG with full period. fails some Diehard tests. |
| ANSI C LCG |
|
Avoid this generator – poorly designed multiplier. |
| VS2013 C++ LCG |
|
Do not use for statistical or security purposes. |
Lagged Fibonacci generators
| LFG Algorithm | Features | Usage Guidance |
|---|---|---|
| Xorshift |
|
Great for simulations and modeling but avoid for cryptography. |
| Mersenne Twister |
|
Good general-purpose PRNG but not for cryptography. |
| WELL generators |
|
One of the best general-purpose PRNGs. Preferred for simulations requiring quality. |
| PCG family |
|
Excellent general-purpose PRNG with a well-engineered structure. |
Cryptographically secure PRNGs
| CSPRNG | Features | Usage Guidance |
|---|---|---|
| Blum Blum Shub |
|
Suitable for high-security cryptographic applications despite low speed. |
| CryptGenRandom |
|
Avoid CryptGenRandom due to known flaws and backdoors. Use alternatives. |
| /dev/urandom |
|
Reasonable OS-provided CSPRNG but may prefer standalone libs. |
| Hash_DRBG |
|
Secure and robust but faster alternatives available. |
| HC-128 |
|
An excellent performer – highly recommended. |
True random number generators
| TRNG | Features | Usage Guidance |
|---|---|---|
| Hardware RNGs |
|
Convenient built-in TRNGs but beware potential weaknesses. |
| Atmospheric noise |
|
Effective entropy source but slow bit generation. |
| LavaRnd |
|
Interesting source but prefer faster, cheaper options. |
| Random.org |
|
Solid Internet-available TRNG source. |
| TrueRand |
|
A premium TRNG solution for applications requiring high security. |
Conclusion
Choosing the right random number generator involves carefully weighing factors like security needs, speed, randomness quality, reproducibility, and implementation complexity. For cryptographic purposes, a robust and well-tested CSPRNG like HC-128 is recommended. General simulation and modeling applications can take advantage of optimized PRNGs like PCG and WELL generators. For less demanding uses like games and web applications, the xoshiro256** algorithm provides excellent performance. Relying on default system RNGs is not advised as they often have known flaws. Proper statistical testing is always required to quantify randomness quality and avoid bad RNGs regardless of claimed specifications.
