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
[Dilbert](https://imgur.com/random-number-generator-bwFWMqQ) and [xkcd](https://xkcd.com/221/) compulsory references.
A computer can generate random numbers by measuring some external phenomenon with excessive number of digits necessary to fully capture the phenomenon at hand. If you do so for a suitable signal, the rightmost digit(s) of your input data are truly random. Say, record sound but only keep the last digit of each sample. This digit will be mostly thermal noise of the microphone and its electronics, and it is random. To get big enough number, you need to then gather multiple samples, see (*) at the end if interested in this detail.
Siri is unlikely to do anything so complicated. It will just call its own built-in random number generation routine. This might return a truly random number (if Apple has chosen to do so, in which case the number will likely relate to least significant digits of some internal signal to the phone’s microprocessor, like its internal operating voltage measurement). Just equally likely, they might just return a “pseudorandom” number. This means a number derived from something seemingly random like the current time at the time your query with a simple mathematical function that tries to make numbers appear random. The latter are also the type of “random” numbers you would use to have random events in computer games (as they are much faster to generate when nanoseconds count, a true random number from, for example, incoming sound would take about a millisecond to generate).
But, with a modern microprocessor in the phone, both alternatives are equally likely. You would not be able to tell the difference between the two for the purposes of Siri giving you a few random numbers every now and then. They both appear equally random to you, or to any other observer not Siri.
(*) Computers of course work in binary, and most analogue input signals are actually presented by an integer. The last decimal will in reality be the least significant bit of an integer variable that represents the analogue input signal. To get a number from 1 to 10 with approximately equal probabilities, you need to gather (much) more than 4 bits (which would give you 16 possible numbers). Say, gather 16 bits. Turn them into a number from 1 to 65536 and keep the last decimal digit. Not perfectly uniform. Not very efficient. But would work just fine. Of course, to avoid the hassle of implementing such a thing yourself, the microprocessor already contains a built-in instruction to do just this. It likely also gathers the input data before you ever ask for the number so that it can give (the first few) random numbers instantly and will only then have to wait a while to give more such random numbers should you ask way too often. This is why things like games would not use these numbers.
There are a couple levels this could be happening at.
Most basic is that you have an algorithm that is chaotic (small verieties in input produces large verieties in output) and then feed it a predetermined number. For the next number just feed the previous number in. This is good enough for a casual user but if you look closely at the data you can reverse engineer the algorithm and thus predict future “random” numbers, this is probematic if you’re trying to stop a hacker.
A more advanced way is to find a more random starting number. A general list from less random to more random is: the exact current time, the exact value of some real life sensor (CPU temperature, microphone noise, camera input etc) or a quantum random number generator. The first is very easy to implement but can be predicted with enough effort and tries. The last is absolutely impossible to predict but very costly. Most modern applications use the second since it’s almost perfect and reasonably cost effective.
“Random” in this case means that the results could never be recreated or duplicated. This isn’t how computers work. As u/km89 stated, they seed an algorithm with numbers that influence the output. If you seed the same numbers, you’ll get the same output.
In most cases, though, this is more than sufficient. The seed could be the precise date and time + the geolocation of the device + the CPU temperature and measure of ambient sound near the PC and your number is going to be hella “random”…but if you know the inputs and put them into the same mathematical calculation, you’ll get the same output.
In a more ELI5 answer, Siri were to generate their random number based upon the precise date and time it was asked, everyone in that same time zone, asking the same question, at the exact same time, would get the same “random” answer. Fortunately, the basis for random number generation is more complex than that.
The most basic forms of random number generator basically cycle one number into the next and next and next in a manner that is very hard to predict.
Essentially, they’re actually cycling very very very big numbers, but only ever show you a small portion of it. You don’t know enough of the big big number to figure out the next one.
But that means if you start at 0, you always get the same number sequence. So computers use something a little unpredictable to start off. The most basic form is to use the exact time, which is very hard to synchronize.
More complex random number generators may incorporate more unpredictable things so that a user couldn’t guess what’s going to pop out. These could be things like disk latencies, network traffic metrics, background radiation levels, or even specific devices that measure radioactive decay.
For an ELI5 the answer is really just Math. It can’t get an actual random number, there’s no computer function that could be truly random. But you can do stupid stuff to make the rough equivalent.
Me at 3:30:46.0432 pm(computers are very precise) Give me a random ⁴ digit number.
Computer: I’ll take the 4 digit fraction of a second, 0432 for starters, a human won’t be able to accurately guess or cheat anything that is so precise. But maybe a computer could. Or maybe a computer with certain hardware only calculates every so often and so there’s a heavy bias towards intervals of a second it actually runs calculations. So let’s mess with it.
Add the MM:DD(0905) as a 4 digit number, discard a 5th position if it occurs. New value is 1337. Keep going.
How many seconds has the PC been on? 60456? Let’s multiply them. 80829672. Okay, let’s get back to 4 digits, discard the right most 2 digits and take the 4 after that then discard the rest. New number is 8296.
What’s the Serial number of the CPU of this machine? Add it and take the last 4 digits for our number, now 6743.
Here’s your “random” number, 6743
Is that random? No, it’s not. But I’ve taken steps to introduce enough external unknowns, cheated the math and made it virtually impossible to be predicted that you might call it random.
This depends on the implementation. The non-secure way was to use a number that’s always changing, like the current time, as a “seed” then perform operations on that number repeatedly to generate new numbers. The output is predictable if you know the seed number, but as long as the seed number is truly random, it’s considered “good enough.” The problem of course is that using the current time doesn’t meet the bar for “good enough,” so it’s not really suitable in situations where you need truly random outputs.
Producing a truly random seed number is the real trick here. Some systems have sources of randomness (Linux has /dev/random) that read things like electrical signals from hardware to generate random numbers, but the quality of said outputs is debatable and system specific. You can also use things like camera outputs. Going further, there are dedicated hardware systems that use anything from electrical measurements to radiation measurements in the presence of fissile material.
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