Building a Pseudorandom Number Generator

In less of 50 lines of Python code

In my article “ How to get an unbiased RNG from an unbalanced one ” I showed how to extract randomness from any kind of source. Now the aim is to build a pseudo random number generator from scratch!

“Why do I need a random number?”

The importance of random numbers is not in the number itself (they are common numbers, if taken individually) but in the way they are generated.

Modern technology is based on these numbers: communication protocols, cryptography, games do heavily usage of them and their whole security and unpredictability depend on them.

Let’s say you want to create a game were the system throws a coin and the player places a bet (with real money) on the result. If the player is right, then he has a reward (in money) otherwise he loses the money placed. If your coin is really fair (or unpredictable) then you have nothing to worry about.

But what happens if the players can predict with an high rate of precision the result of the next toss? Or if they can predict the next result according to the last three throws? The answer is obvious.

Natural generators

Nature offers some sources of randomness, but they are very expensive to use.

In macroscopic environments there are few sources, such as climate changes or the cosmic microwave background. These kind of generators are very expensive: immagine to buy a system that connects you to a satellite that measures the CMB variations and sends the result back in a few milliseconds. The cost is around 400 ~ 500 million USD.

Ok, I took an extreme case but in general it’s not convenient at all, considering costs and performances.

In microscopic the entire environment is driven by chaos: as far as we know, it’s a probabilistic world; but again it’s very expensive managing this kind of source. Balancing perfectly a particle’s quantum state it’s not a simple task.

Pseudorandom generators

For these reasons we always find convenient to build a generator in our machines (computers, smartphone, TV, etc… ). Also having a more compact way to calculate a random string is always good: if your system extracts a sequence from the local temperature in μK, anyone can reproduce the same sequence by positioning a sensor near yours; or even anyone can manipulate the detections and take control over your sequences.

A computer uses a CPU to execute the instructions, and the CPU is based on a deterministic mechanism. How can we create randomness from an environment that do not have any source of randomness?

Before I answer to this, let’s define a pseudorandom number generator (PRNG). From here I will treat PRNGs that work with bit (0s and 1s), but it is very easy to verify its properties for other cases since it is possible to encode a binary sequence in a number.

The theory behind

Given an initial seed, a PRNG produces a sequence of bit indistinguishable from a sequence produced by a real random source.

Indistinguishable means that there is no algorithm executable in polynomial time on a probabilistic Turing machine that can decide if the given sequence is random or calculated. That is, no randomised algorithm can say if a string produced by a PRNG was calculated deterministically or extracted by a random source.

Hence, here it is a definition of PRNG: it’s an algorithm executable in polynomial time on a deterministic Turing Machine that calculates a function G such that

with l as a monotonically increasing function. That means the output is always longer than the input (seed).

Also, for every algorithm in D belonging to BPP class , for every polynomial p and for every integer k sufficiently big: