Humans and computers are really bad at being random. An article recently published by the FT examined how people behaved under seemingly random situations and how efficient computers are at predicting our decisions even when we aim to act as randomly as we can.

Computers are equally bad at acting randomly; yet this hasn't stopped us from attempting to develop algorithmic approaches to generating randomness. Random number generators have many applications, from generating worlds , running probabilistic simulations to cryptography.

Randomness can be split into two categories, True Randomness and Pseudo Randomness. True random may only appear in life and nature where it is impossible to predict the next state despite knowing the current state. On the other hand even though pseudo random appears unpredictable it can be replicated if all the starting conditions are known.

Quality of Randomness

There are several qualities to the algorithms that provide us randomness by which we can compare them. The first quality is the algorithm's "period", the number of time we can generate an output before the numbers start to repeat themselves. The second is the number of dimensions the algorithm can pass the spectral test.

In the 1940s von Neumann presented the middle-square method for computing random numbers and it worked as follows:

1. Take an n-digit number
2. Square it
3. Take the middle n digits from the result

The alternative was to find a random number from a book. Whilst there's no set period for the middle square method it is often short and unpredictable which proves to be inconvenient in most applications.

An improvement was made in the 1950s with the development of linear congruential generators. However these fall short on spectral tests which means they start to develop hyperplanes in larger dimensions (the English translation: you start to notice patterns in 3D).

There are a number of tests that are used to measure the quality of a random algorithm which have become known as the Diehard tests. Among them is a suite of tests called "Craps test" where the algorithm plays 200k games of craps and the count of wins and throws should follow a specific distribution.

Contemporary Randomness

All algorithms that generate random numbers start with what is known as a seed. The seed is a number that is used to provide an initial state that all future states are based on. This allows us to replicate random generation or seemingly random simulations when provided with the initial seed.

There are some situations where a seed is not explicitly given when generating something random - however typically your computer will use the current time as a substitute for the lack of explicit seed.

Most contemporary languages such as python use an algorithm called the "Primitive Twisted Generalized Feedback Shift Register Sequence" this is known more commonly as the Mersenne Twister. Due to the existence of a Mersenne prime constant in the algorithm. You can read the C implementation of MT in the python source.

A note on Mersenne primes: these are prime numbers that are (2^n) - 1. One less than a power of two. These primes happen to be the quickest to prove as prime and therefore make up all the largest known prime numbers.

The period of the Mersenne Twister is (2^19937), which is a number I don't have time to type out. 19937 happens to be that Mersenne prime number in the algorithm and the algorithm passes spectral tests up to 623 dimensions.

Cryptography

The realm of cryptography relies on crypto-secure pseudo random number generators (CSPRNG). These are used when generating a password or private/public keys for encryption like RSA. They are required to be both random and unpredictable. Unfortunately the Mersenne Twister isn't safe for cryptography since with enough observations it becomes predictable. As evident in the blog series: Cracking Random Number Generators

Over time we've seen the pseudo random algorithms required in cryptography being broken and methods discovered in order to predict the random number used in the system. Cloudflare proposed a solution to this, instead of having the CPU generate a number using a predetermined algorithm, have a wall of lava lamps and take a photo of the wall whenever you need a new number. This works because images are stored on a computer as numbers and there is naturally occurring randomness which is extremely hard to reverse engineer.