Introduction to Pseudorandom Number Generators¶
Overview¶
A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm used to generate a sequence of numbers that approximates an absolutely random number sequence. Generally, a PRNG relies on an initial value, also called a seed, to generate the corresponding pseudorandom number sequence. Once the seed is determined, the random numbers generated by the PRNG are completely deterministic, so the generated random number sequence is not truly random.
Currently, PRNGs play an important role in many applications, such as simulation (Monte Carlo methods), electronic gaming, and cryptographic applications.
Strictness of Randomness¶
- Randomness: Random numbers should have no statistical bias and should be a completely chaotic sequence.
- Unpredictability: The next number cannot be predicted from past sequences.
- Non-reproducibility: Unless the sequence is saved, the same sequence cannot be reproduced.
The strictness of these three properties increases in order.
Generally speaking, random numbers can be divided into three categories:
| Category | Randomness | Unpredictability | Non-reproducibility |
|---|---|---|---|
| Weak PRNG | ✅ | ❌ | ❌ |
| Strong PRNG | ✅ | ✅ | ❌ |
| True random numbers | ✅ | ✅ | ✅ |
Generally, the random numbers used in cryptography are of the second type.
Period¶
As we mentioned earlier, once the seed that a PRNG depends on is determined, the random number sequence generated by the PRNG is essentially determined. The period of a PRNG is defined as follows: for all possible starting states of a PRNG, the maximum length of a non-repeating sequence. Clearly, for a PRNG, its period will not exceed all its possible states. However, it is important to note that encountering repeated output does not necessarily indicate the PRNG's period, because the PRNG's state is generally larger than the number of output bits.
Evaluation Criteria¶
See Wikipedia, https://en.wikipedia.org/wiki/Pseudorandom_number_generator.
Classification¶
Currently, the main common pseudorandom number generators include:
- Linear Congruential Generator, LCG
- Linear Regression Generator
- Mersenne Twister
- xorshift generators
- WELL family of generators
- Linear Feedback Shift Register, LFSR
Problems¶
Typically, pseudorandom number generators may have the following problems:
- For certain seeds, the period of the generated random number sequence may be relatively small.
- Uneven distribution when generating large numbers.
- Close correlation between consecutive values; knowing subsequent values can reveal previous ones.
- Highly uneven sizes of values in the output sequence.