How does a computer program generate random numbers? Example: when you ask Siri to give you a random number between 1 to 10, how does it come up with that number?
In: Mathematics
Ok – let’s do this.
Computers are generally design to be deterministic, that is, for the same input, they should always produce the same output. Whilst it’s actually difficult to define what we mean by “a random number”, a desirable property of a process which outputs such a thing a that it should be unpredictable. There are other desirable properties as well – the numbers generated should be uniformly distributed (so that each one is equally likely to appear) and we can go further – every possible sequence of numbers should also be equally likely to appear. The numbers generated should avoid bias.
There are two approaches that are used. The first is to use a pseudo-random number generator. These are algorithms which produce a random-seeming sequence but are actually completely predictable if you have access to a “hidden value” (called a “seed”) which is actually used to calculate all the “random” numbers it produces.
These pseudo-random numbers can be generated in such a way that they satisfy all of the properties we desire from a process which makes random numbers except for one: they are predictable.
Also, the sequence will eventually repeat, and it is possible first a clever hacker to recognise the sequence of numbers and therefore work out the seed and then be able to predict the next numbers. This would be bad if you were relying on these numbers to protect some secret, for example your credit card number.
To actually create a genuinely unpredictable number, we need a source of randomness. There are plenty- for example you could measure the sound from a microphone and just take the volume level at a particular instant. Or the temperature of the CPU at a particular instant. These are called “entropy sources”.
The trouble with these is if you measure them too often, they become predictable: the temperature of the cpu a millisecond later is quite likely to be close to its previous temperature.
The result usually that generating random numbers from an entropy source is very slow: you will get random numbers, but not many of them.
So we combine both approaches: we use the genuinely random but slow number from the entropy source as a seed to generate some pseudo-random numbers. But not too many, because the more you produce, the more likely it is that someone will be able to work out the seed from the sequence.
By the way, the difference between normal and cryptographically secure pseudo-random number generators is how hard it is to guess the seed if you have seen the sequence it generates. They are generally a lot slower.
Latest Answers