How Computers Generate Random Numbers

Erin Herzstein

Published in

Level Up Coding

9 min readJan 7, 2021

Believe it or not, rule-following machines can actually be pretty spontaneous.

Index

True Random Number Generators (with examples)
Pseudo-Random Number Generators (with examples)
Comparing The Two: TRNGs vs PRNGs
Summary Table

I think we’ve all been in one of those group situations where there is a dreaded task that has to be done, but nobody wants to do it. Whether it’s breaking bad news or cleaning up after a project, somebody has to take one for the team.

So how do you settle it? You can’t just have someone pick a random number, because well, they can always just change their number to spite their least favourite group member. What you can do is ask the computer to do it for you. But was the number generated really random? How does a computer, a machine defined by its adherence to instructions and formulae, generate a random outcome?

Before we get started, it’s important to note that random generation is useful in more ways than settling a group dispute. Randomness is at the forefront of gambling, video games, statistical sampling, and most notably, cryptography¹. If they couldn’t be unpredictable, our devices would lack essential security features and be far more vulnerable to cyber-attacks.

There are two main methods that a computer generates a random number: true random number generators (TRNGs) and pseudo-random number generators (PRNGs). The former uses some phenomenon outside the computer for its number generation, whereas the latter relies on pre-set algorithms to emulate randomness².

If that doesn’t make any sense yet, don’t worry — there’s lots more on it to come.

True Random Number Generators (TRNGs)

Nuclear Random Number Generator by M.daSilva

True random number generators (a.k.a. hardware random number generators), produce numbers by harvesting entropy, meaning they collect information from an unpredictable environmental condition.

In order to convert some physical phenomenon into a number, a TRNG must have several hardware components³:

A transducer: this converts the phenomenon being measured to an electrical signal
An amplifier: this increases the amplitude of random variations in the signal so they can be identified by the device
An analog-to-digital converter: this converts the signal into a digital number

Some examples of TRNG sources include atmospheric noise, time, and radioactive decay.

Atmospheric noise

This uses processes occurring in the atmosphere for its RNG. Most often, it’ll capture the static generated by lighting flashes, which occur roughly 40 times per second⁴. This method is pretty much as unpredictable as they come.

Random.org is known to use atmospheric noise to generate random outcomes for all kinds of different scenarios. Highly recommend checking them out!

Time

Some TRNGs will use the exact nanosecond that you press the keys or click the mouse to generate a random number. For example: if you wanted to generate an integer value between 1 and 10, and you press the enter key at exactly 4:50:52.287503482 PM (yes I just slammed my keyboard), then the computer might take that last digit and use “2” as output.

Radioactive decay

When a nucleus is unstable, there is no way of predicting when it will decay. This makes it an ideal candidate as a source of entropy for true random number generation.

If you’re interested in learning more about radioactive decay and RNG, you might want to take a look at HotBits by FormiLab.

Pseudo-Random Number Generators

PRNGs rely on algorithms to generate sequences of numbers that appear to be random. As suggested by the prefix “pseudo”, the sequence isn’t actually random, it just looks it. The two main components of a PRNG are an initial value or seed, and a pre-set algorithm.

Here’s how it works. The generator must:

Receive an initial value or seed as input
Generate a new number by applying a series of mathematical transformations to the seed
Use the value obtained as the seed for the next iteration
Repeat the process until the desired length is achieved

PRNGs are deterministic and periodic. They are deterministic because once the algorithm and seed are defined, nothing can change the numbers that are outputted. Each consecutive number in the sequence is related to previous ones; this is known as a recurrence relation. PRNGs are periodic, meaning they repeat themselves after a certain number of iterations. A good PRNG algorithm should have a long period.

Let’s look at some examples: the linear congruential and the middle-square generator.

Note: there are countless other types and variations of PRNGs, featuring some pretty cool-sounding ones like Philox and Mersenne Twister.

Linear Congruential Generator

The linear congruential generator (LCG) made its first appearance in 1958, and is to this day one of the most popular PRNG algorithms⁵.

It follows a recurrence relation of this format:

Where

X₀ is the seed or start value (0 ≤ X₀ < m)
a is the multiplier (0 ≤ a < m),
c is the increment (0 ≤ c < m), and
m is the modulus (m > 0)

Let’s try an example using the procedure outlined above. Let X₀ = 235, a = 2,398, c = 8,738, and m=1,000,000.

Step 1: Receive an initial value or seed as input.

Great! We’ve already done that: X₀ = 235.

Step 2: Generate a new number by applying a series of mathematical transformations to the seed.

Using the values of a, c, and m, we can complete the calculation:

1,000,000 fits into 572,268 0 times, leaving a remainder of 572,268.

Step 3: Use the value obtained as the seed for the next iteration.

Our X₁ is 572,268, so to get our X₂, we just have to use our formula again:

1,000,000 fits into 1,372,307,402 1372 times, leaving a remainder of 307,402.

Step 4: Repeat the process until the desired length is achieved.

By repeating steps 1 to 3, we find that the first 10 numbers of this sequence are 572268, 307402, 158734, 652870, and 590998. Looks pretty random, doesn’t it?

If you don’t feel like doing all those calculations by hand, I created a method that returns a sequence of values generated by a linear congruential algorithm. Here it is rendered in Java:

public static String generateRandomNumbers(int length, long x0, long a, long c, long m)
 {
  StringBuilder sb = new StringBuilder();
  
  long x[] = new long [length];
  x[0] = x0;
  
// applies a series of mathematical operations to a term (x[i]) in order to find the next term in the sequence (x[i+1]); this repeats until the desired length is achieved  for(int i = 0; i< length-1; i++)
  {
   x[i+1] = (long) ((a*x[i] + c) % m);
   sb.append(x[i+1]+" ");
  }
  
  String results = sb.toString();
  
  return results;
 }

Middle-Square Generator

The middle-square method was invented in 1949 by Jon von Neumann, and works by squaring the seed value and extracting its middle digits to be used as the next seed.⁶

Note: this method is considered to be one of the less practical algorithms because it tends to have a short period. A lot of seed values quickly result in the repeating of zeros or other numbers.

For this method to work, there are a couple of conditions that need to be met:

The squared seed must have at least twice the number of digits as the seed. If this is not the case, leading zeros are added to compensate.

For instance, if our seed is 20, then seed² is 400. 400 has 3 digits and 20 has 2. Since 3 < 2*10, we add a leading zero to make the squared value 0400, and our output is 40.

The seed must have an even number of digits. This is because squaring an odd number does not guarantee that there will be middle digits to extract.

If our seed is 617, then seed² is 380689. Here the number of digits in seed² is 2 times the number of seed digits, so that condition is met. However, there are no 3 middle digits that work. This can be rectified by adding a leading zero to the seed: 0617 → 00380689 → 3806.

Once again, we can create a Java program that takes a seed as input and generates a sequence of numbers.

First, we have to create a method that takes the seed, squares it, then extracts the middle digits:

// String x = seed // int digitsX = number of digits in the seedpublic static String getMiddleDigits(String x, int digitsX)
 {
  String leadingZeros="";
  
// adds leading zeros  for(int k = 0; k < x.length(); k++)
  {
  if(x.charAt(k)!='0') {
   break;
  } else {
   leadingZeros+="00";
  }
  }// squares the seed, converts it to a string array, and obtains the number of digits
  
  String squared = leadingZeros + String.valueOf((long) Math.pow(Integer.parseInt(x), 2));
  String[] stringSquared = squared.split("");
  int digitsSquared = stringSquared.length;
  
  // finds the digit in the squared seed where the next term will start  int start = (int) (digitsSquared - digitsX) / 2;
  String [] newTerm = new String [digitsX];StringBuilder sb = new StringBuilder();
  
// creates the new term by adding digits from the middle of the squared seed to an array  for(int j = 0; j < digitsX; j++)
  {
   newTerm[j] = stringSquared[start+j];
   sb.append(newTerm[j]);
  }  String middleDigits = sb.toString();
  
  return middleDigits;
 }

Then, we have it repeat this process to generate the first 200 numbers in the sequence:

public static String generateRandomNumbers(String x0)
 {
  String x[] = new String [200];
  x[0] = x0;// finds the number of digits in the seed
 
  int digitsX = (x[0]).split("").length;
  
  StringBuilder sb = new StringBuilder();
  
// applies the getMiddleDigits method to create a sequence of seemingly random numbers  for(int i=0; i<199; i++)
  {
   x[i + 1] = getMiddleDigits(x[i], digitsX);
   sb.append(x[i + 1] + " ");
  }
  
  String results = sb.toString();

  return results;
 }

And there you have it! The middle-square generator.

Which Generator Is Better: TRNGs or PRNGs?

Depends on what is meant by “better”.

If we’re talking convenience, PRNG takes the cake. Because they rely on external conditions, most TRNGs require instruments and resources that are both costly and must be consistently monitored for damages. Talk about high maintenance.

When it comes to cybersecurity, TRNG’s your winner. For a sequence true random numbers, there is no relation between subsequent values besides the fact that they come from the same source of entropy. In this way, TRNGs are nearly impossible to predict, and therefore much safer defences against cyber attacks. PRNGs are deterministic; because each number in the sequence relies on previous ones, they are much easier to decrypt.

Pseudo-random numbers are also periodic; they eventually end up repeating themselves. This can be problematic in some cases, but practically-speaking, it is usually easy enough to find a combination of inputs where the period is sufficiently long.