PseudoRandom number generator
In our day to day lives, random numbers have always been important for us. From playing video games, gambling to security implementations requiring cryptography, random numbers are important to secure encryption, be it encryption of messages on your favorite messaging app or securing your personal information on cloud. Beside encryption, they are widely used in simulation and modelling.
But generation of random numbers is non-deterministic and is completely unpredictable. Therefore, a random number generator would generate a number sequence that contains no recognizable patterns or regularities. Hence, when we need to generate similar kind of numbers which are deterministic and are appropriate for statistical analysis, we prefer to go with pseudorandom numbers.
What does Pseudorandom means ?
Pseudorandom number is a number, which appears to be random but is not.
As per wikipedia, Pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG’s seed (which may include truly random values).
In simple words, PRNG generate numbers that appear to be random but are predictable. Here, computer uses a seed value and an algorithm to generate numbers that seem to be random, but are deterministic.
What is a seed ?
A seed is a number used to initialize a pseudorandom number generator.
For a seed to be used in a pseudorandom number generator, it does not need to be random. This number can come from randomness of noise, or the current time in milliseconds.
Once we select our seed, we need to select a suitable algorithm. For now, we will go with middle squares method, i.e. Multiply the seed by itself, then output the middle of the result. Then use this output as next seed and repeat the process as many times as needed.
Same seed same sequence.
The pseudo random sequence must eventually repeat with same seed. This occurs when an algorithm reaches a seed it has previously used, the cycle repeats.
The length, before a pseudorandom sequence repeats itself , is called the period.
The period is strictly limited by length of initial seed. For example, if we use middle squares algorithm, and we use a two digit seed, then the algorithm can mostly generate at most 100 numbers before reusing a seed and repeating the cycle. Similarly a 3 digit seed, can generate at most 1000 numbers, and 4 digit, can generate 10000 numbers before repeating itself.
In the gif image attached, the pattern in blue denotes pseudorandom number generation, where the pseudo random sequence repeats itself, and when an algorithm reaches a seed, the cycle repeats. However, as long as the original seed is ignored, the rest of the values that the algorithm generates will follow probability distribution in a pseudorandom manner. The pattern in white denotes the true random number generator which is non deterministic in nature
Popular PRNG Algorithms
- Mersenne Twister
Mersenne Twister produces 53-bit precision floats and has a period of 2**19937–1. The underlying implementation in C is both fast and threadsafe. The Mersenne Twister is one of the most extensively tested random number generators in existence. However, being completely deterministic, it is not suitable for all purposes, and is completely unsuitable for cryptographic purposes. It is the default random number generator for Python, Ruby, R, PHP, Matlab, and is availbale in C++ as well. - Linear Congruential
It uses a 48-bit seed (the initial data) which is then modified using a linear congruential formula. It is very simple to understand and is defined by recurrence relation: Xi+1 = (A*Xi + C) mod M
where Xi is the sequence of pseudorandom values and Xo, 0 <= Xo <=m the “seed” or “start value”. Even though the generators using this formula are fast and require minimal memory (typically 32 or 64 bits), these generators can’t be used when randomness is a critical issue, like generating keys, session ids etc. The problem with these generators is that once you know the starting seed or the previous value, it’s very easy to find out the next value. This is used for pseudorandom number generation in Java.
To conclude i would quote wikipedia again, “Good statistical properties are a central requirement for the output of a PRNG. In general, careful mathematical analysis is required to have any confidence that a PRNG generates numbers that are sufficiently close to random to suit the intended use.”
