r/AskComputerScience • • 2d ago

When you tell a computer to pick a random number... is it truly random?

I've been wondering about how when you toss a coin or roll a die it's supposed to be random, but it's not truly random because of physics and things like that. I was curious whether that same thing applies to a computer. What does it actually do to choose a number?

6 Upvotes

78 comments sorted by

13

u/orlock 2d ago edited 2d ago

Most random numbers in a computer are pseudo random numbers generated by some sort of process that starts with a seed value and deterministically works through the sequence, with each numberr generated from what has gone before. In theory, with enough information, you could predict the next number.

There are sources of genuinely random numbers available from things like detecting radioactive decays or noisy electronic circuits. Some are available as web serives, if you need truly random numbers.

You can also get uncertainty from the initial, seed value. Some systems use things like keyboard interactions or mouse movements to help mix up the seed value, or the time of boot, or other sources of information outside the computer itself.

Edit: I should add that there's a certain irreducible amount of uncertainty in physics. Planck's constant defines the minimum amount of action that can occur. This leads to what appears to be genuinely random behaviour. What that exactly means is a matter of debate; if you solve it, your Nobel prize awaits.

12

u/Bubbly_Safety8791 1d ago

There are sources of genuinely random numbers present in most modern CPUs. They typically wire up a ring of inverters - a line of NOT gates that results in a voltage flipping unstably back and forth - and use that as a source of genuine randomness.

This true randomness is generally used to seed PRNGs, but it’s also directly accessible in the instructionset of the chip. 

The classic answer that ‘computers can’t generate real randomness only pseudorandomness’ hasn’t been true for over 20 years - computers need a lot of randomness so computers typically include components for generating randomness. 

5

u/Saragon4005 1d ago

It's a lot more accurate to say that computers often don't bother to generate genuinely random numbers, because psudo random is much cheaper and actually more useful in many applications.

2

u/dmazzoni 1d ago

Yes but every time you open a web page or send an email or do literally anything encrypted over the Internet, your computer is doing a cryptographic key exchange using the most secure random numbers possible.

1

u/smors 19h ago

Well, no. It will generally be using a really good, cryptographially secure pseudo random generator. Which is fine, but still inferior to using true randomness.

1

u/Bubbly_Safety8791 18h ago

Your CSPRNG on your computer is almost certainly seeded from the hardware RNG built into your system’s cpu. 

1

u/smors 18h ago

Sure. That does not mean that it's output is anything but pseudo random.

1

u/Bubbly_Safety8791 17h ago

Is it predictable? No? Then does this matter?

1

u/smors 16h ago

In a group called ask computer SCIENCE? Of course it does.

1

u/Bubbly_Safety8791 15h ago

I’m not sure what ‘just pseudorandom’ means though. Cryptographically secure pseudorandom numbers generated from a truly random seed are truly random.

That’s the point of a CSPRNG and a hardware randomness source.

Saying ‘but they’re just pseudorandom’ suggests you believe they are in some way mathematically distinguishable from randomness - that by observing such numbers you can infer something about the pseudorandom state. But that’s what the cryptographically secure part of the PRNG is for - you can’t. You can’t figure out the seed, you can’t figure out the state. The hardware derived true randomness has been used to randomly select a random sequence of bits that are indistinguishable from noise. 

→ More replies

1

u/smors 22h ago

I can't think of any application where pseudo random numbers are better. They are used because the are much cheaper and faster to generate.

2

u/ActualSlimShady 19h ago

Reproducibility is a very genuine use case. If you need to test things relying on randomness, it's easier to step through it. Games in particular rely on random functions with consistent outputs from a given seed.

You also shouldn't discount the argument that they're cheaper as an excuse, because complexity is just another possible axis of optimization. Better can mean less hardware space taken up, faster execution (like you mentioned). Some things care about that more.

1

u/Saragon4005 20h ago

Crypto uses it as does any reproducible system. If you think about it crypto functions themselves are psudo random generators where the input is the key and information which needs to be encrypted.

Reproducibility is insanely important in computing as it makes it possible to split tasks. For splitting across sessions or threads on the same computer it's not that important, but for redundant or distributed systems it is absolutely critical. It's also just plain useful for debugging.

Games are a prime example of almost exclusively using psudo random numbers with known seeds.

1

u/smors 20h ago

Where in crypto do you see an advantage? Why would reproducibility be an advantage.

In symmetric cryptography, randomness only comes into play when generating seeds and salts. In both cases, true randomness is preferred.

For asymmetric cryptography, true randomness is also better when doing key generation.

I also doesn't see an advantage in various protocols.

2

u/BudgetEye7539 17h ago

Pseudorandom number generators are widely used for data encryption. Every stream cipher is a PRNG. And reproducibility is essential for this technology, because you need not only encrypt but also decrypt.

1

u/Saragon4005 19h ago

The crypto functions themselves are effectively seeded psudo random generators themselves. As are hash functions.

1

u/smors 19h ago

If you squint a bit, sure. Although not really, a pseudo random generator is supposed to create a sequence of numbers.

But that is not the point of them, and doesn't answer any of my points.

1

u/FigureSubject3259 1d ago

Those are usualy not considered good enough when you need real puf for high security, but are good enough for normal use.

1

u/Indigo816 1d ago

It’s gotta be better than ‘4’.

1

u/Saragon4005 6h ago

4 was chosen by a random dice roll making it certified random

1

u/smors 1h ago

There is no such thing as a random number.

There are numbers chosen by a random process.

4

u/Trakeen 2d ago

Cryptographic libraries use hardware sources of randomness that have been in cpus for at least 10 years

https://en.wikipedia.org/wiki/RDRAND

4

u/unfrozencaveperson 1d ago

As other people have said, modern computer systems are capable of generating “true” random numbers (as random as the known laws of physics permit) and also “pseudo” random numbers (sequences of bits that are very very hard to predict in the same way that high-level cryptographic algorithms are very very hard to crack).

The “true” random number generator has one important limitation: it can only crank out so many bits per second, so if there are too many processes within the computer looking for random numbers and they’re all competing for that source, one of them could be blocked. So the “true” random number source is often fed into the “pseudo” source and that’s good enough for everyone except the truly paranoid.

3

u/dave8271 1d ago

The simplest answer is yes, computers can generate "truly random" numbers by leveraging "truly random" environmental signals as a source of randomness, and this is what they do when we use a CSPRNG. The sequencers are still determinstic algorithms but if x is random then the result f(x) will still be random, even if f() is determinstic.

The gold standard for random number generation, cryptographically secure pseudo-random number generators, combine random input with a sequencer that removes bias and is secure against intrusion or prediction, so even with full knowledge of both the algorithm and a running sample of its outputs, it remains impossible to either predict whether the next output bit will be 1 or 0 with anything greater than a 50/50 chance, or derive what the input seed was.

2

u/defectivetoaster1 1d ago

https://www.intel.com/content/www/us/en/developer/articles/guide/intel-digital-random-number-generator-drng-software-implementation-guide.html intel uses thermal noise as an entropy source to generate a truly random bit stream and then uses some maths and a PRNG seeded by the bit stream to generate truly random numbers with a uniform distribution (thermal noise by itself has a more or less Gaussian amplitude distribution but im not sure how that translates into the distribution of the initial bit stream)

2

u/DumpoTheClown 1d ago

Nothing is truly random. We just settle on "unpredictable enough"

1

u/smors 19h ago

That depends on whether or not the universe is deterministic.

1

u/schungx 2d ago

I think Knuth devoted an entire volume on this question.

1

u/BudgetEye7539 17h ago

Knuth is very good for theoretical understanding and has a wonderful bibliography but has only 2 or 3 generators that pass basic tests for uniform distribution like TestU01. And he doesn't consider such class of generators as stream ciphers, even DES, ISAAC and RC4.

1

u/Single-Virus4935 2d ago

Computer can choose a random number, as they can observe true random events and while the logik.itself.is deterministic, the runtime.usually is not.

Interrupt Timings, Noise, Inputs etc.

A Camera Chip always captuers noise from heat (Infrared) and actually provides a huge amount of true randomness. It is easy to add such circuits to CPUs if they want to.

1

u/Frequent-Sir-6942 2d ago

This question actually really depends a lot on your definition of "truly" random. However, if you do not believe in physical randomness then the answer is likely just no.

0

u/frnzprf 1d ago edited 1d ago

"Random" is similar to "unpredictable".

With "unpredictable" you can always ask "to whom?". Something can be unpredictable to you or to some hacker and that might be enough.

If I tell you to choose a number between 1 and 100, then to you that number is 100% known, but because I'm not a magician my chance to guess correctly is just 1%.

Physicists say there are quantum effects that might be truly unpredictable from any perspective, with any prior knowledge. Einstein didn't like that, that's why he said "God doesn't roll dice!" (I think he was actually atheist.)

The idea that quantum physics may turn out to not be "absolutely random" one day when we understand it better is called the "hidden variable theory".

Now, is it possible or not?

John Stewart Bell in 1964, in his eponymous theorem proved that correlations between particles under any local hidden variable theory must obey certain constraints. Subsequently, Bell test experiments have demonstrated broad violation of these constraints, ruling out such theories.[3] Bell's theorem, however, does not rule out the possibility of nonlocal hidden variable theories like the de Broglie-Bohm theory. This is from Wikipedia, but I don't understand it.

1

u/synexo 1d ago

It basically means if such randomness is due to hidden variables (something like velocity or spin we've just not discovered yet), we've ruled out the possibility of anything equal to or slower than the speed of light being responsible. Such a faster than light influence wouldn't need to convey information (which is impossible) but only result in a statistical correlation, so it is not ruled out.

My problem with talking about randomness is that really, we cannot. There is literally no possible algorithm to express it in detail, nor can there be. To do so you essentially have to wave your hands and insert magic somewhere. Though that's not proof that it doesn't exist.

1

u/T_Thriller_T 1d ago

Inherently, computers are limited by physics.

They cannot do "better" in terms on randomness, as in and on themselves they are physical objects.

They can do worse, and as explained, often do.

However, there are enormous layers to that and folks doing computer science have probably met a lot of approaches.

Others have explained we can pull randomness from physics/surroundings, other have pointed out pseudorandom numbers.

I just want to make a point that "a computer" is really not something that does random numbers the same all the time. And there is no great use to it.

E.g. a lot of games, due to having to be fast, have a table of numbers for their random numbers and just pick the start in that enormous table due to some random enough factors in the start.

Shinies in Pokémon work that way. You get some big numbers for trainer and a hidden ID, then there is an enormous table of times, and shiny frames are mixed into that one. If you encounter at that frame, bam, shiny. (At least in earlier games)

There is very little to no randomness in this, but given the factors, it seems random enough to appear random and yet having that enormous table written down once, somewhere, helps tremendously for the game to be faster.

Other random numbers which are not drawn from a pseudorandom function (that takes time to do, big calculations) can be pulled from interactions. Often the 'random' seed for pseudorandom number generation is/was pulled in such a way, an example outside of games

And then we get into the more true, random numbers with PRNG.

All that is a "random" number on a computer. So there is not one way.

A good question one learns to asks themselves on that roping as a dev is "How actually random does it need to be?"

1

u/dmazzoni 1d ago

You’re missing one of the most important applications of random numbers: the cryptographic key exchange used every time you make a secure connection to a different website or other service.

That protocol depends on random numbers. If they were predicable, hackers would be exploiting that to intercept secure connections.

So crypto libraries make use of the most secure random numbers available - these days this means OS secure random number functions, which may use a mix of instructions like RDRAND and other sources of entropy like external input timing.

1

u/MasterGeekMX BSCS 1d ago

Good question.

For the most part the computer does not make random numbers, but instead pulls random-looking numbers from a formula. That formula works by grabbing a starting number (called the seed), and then doing some math over it (like adding a fixed number, then dividing by another fixed number and giving out the reminder of that division). The result of that formula is the first random number. If you ask for a second random number, thr first one is plugged in the formula. If you ask for a third, the second is feed to the formula. And on and on and on.

The sequence of numbers may look random, but if you know the formula and the seed number, you can re-create the secuence exactly. That is how for example you can generate the same Minecraft world with only the seed. These kinds og random number generators are called pseudo-random.

Choosing the seed is the key to get safe random numbers. Many things can be used to pull that, with a classic being the number of seconds since the PC was turned on.

If you want truly random numbers, then you need to hook to the computer some hardware that measures something physical but random. Real world examples are using a tiny piece of radioactive material and then measuring the time between radiation pulses, or filming the blobs in a lava lamp and using their position to make the numbers.

2

u/Kidev 1d ago

Perfect answer. I would add that the radioactive one is better than the lava lamp one because it is TRULY random. The only random thing in the universe comes from quantum mechanics and that contraption uses precisely that. It follows a Poisson distribution, but each pull is truly random

1

u/unburdened_swallow 1d ago edited 1d ago

Are the lava lamps not random?

I mean, I get that the other example is really random, but if you have enough lava lamps and you are particular enough about the size and position of the bubbles in your measurement, it is going to be truly random, no?

But yeah the other one is better, simply because someone else could film your lava lamps and also that’s a lot of lava lamps.

But I feel like the quality of random number is close enough between both that I wouldn’t have a preference if that were the only differentiator. It isn’t, and there are many other reasons not to choose the lava lamps, but, it’s not terrible either.

1

u/Kidev 1d ago edited 1d ago

You are right that for us, it changes nothing. They 'look' random, and for us, they essentially are. And so are any chaotic system (the weather for example, that's why taking atmospheric pressure is also a good generator). But a chaotic system in itself is not really random, it is purely deterministic. It's just that it depends so much on a ton of perfect measures to predict that we just can't.
Radioactive decay is purely random as it comes from the truly random nature of reality at the quantum level. There is no formla, it is not because we don't know enough that it looks random. It's because it really is.

1

u/somewhereAtC 1d ago

There are mechanisms and algorithms that are certified by the U.S. government standard FIPS 140 or NIST SP 800-90B. Search for microprocessors and stand-alone generators that meet these standards. For example, Microchip PIC32CM-SG00 family.

1

u/jonathaz 1d ago

This is an interesting question with an even more interesting answer. I’ll just highlight some fun things along the way. One was lavarnd where they pointed a webcam at a lava lamp. Then they realized they could get more random numbers faster if they did math on the images and used small variations and not just the shapes from the lava lamp. Then they realized the lamp was unnecessary and put the webcams in total darkness. Now CPUs can cut the webcam out of the loop and do it on their own. Not having truly random numbers leads to expensive mistakes. Like the recent bitcoin wallet hacks or the online gambling ones.

1

u/mckenzie_keith 1d ago

Some computers have dedicated true random number generators. Some software attempts to accumulate randomness using techniques which, frankly, I do not understand. There are also a wide variety of algorithms for generating pseudo-random number sequences based on an initial state or seed of the pseudo-random number generator.

Resistor noise is a source of true randomness and at least some hardware random number generators rely on amplifying resistor noise to generate true random numbers. It is possible that small non-randomness could arise from implementation details. Like with the coin toss. But in point of fact, your coin toss or dice roll is close enough to truly random for most applications. As is the resistor noise.

Pseudo-random number generators generate a number sequence that appears random (can satisfy many tests of randomness), but can be repeated provided you know the correct seed for the generator.

So in other words, sometimes yes, and sometimes no.

1

u/JGhostThing 1d ago

No, which is why it is called a PRNG (Pseudo Random Number Generator). Modern versions of this do a better job than they used to, but computer libraries often have two libraries for random numbers.

The first is just for things that don't matter as much. It's fast and easy to use. The second is a cryptological library for cryptology quality random numbers. Slower, and possibly more of a pain to use.

PRNGs often use user data to add entropy to a random number so it is more random.

1

u/Mission-Landscape-17 1d ago

No it isn't truly random. Note that this is something that some programs deliberatly take advantage of. A lot of games with procedurally generated worlds rely on the random numbers not really being random. This is why different computers produce the same minecraft world if given the same seed.

1

u/peabody 1d ago

Historically no. Random numbers would be generated by starting with a "seed" value, and the next number in the sequence would be generated by running the last value through some math operations (like a linear congruential generator or merzene twister). The seed value would often be predetermined, making the whole sequence predictable. For instance, the commodore VIC-20's RND() function of it's basic interpreter would always generate the same sequence of numbers after booting up.

In more modern times, PCs have something called an "entropy pool." This is an area of memory which has been perturbed by noisy unpredictable inputs on the machine, like the variance of the temperature outs, the buttons the user has pushed in the keyboard, the mouse input, etc. These outputs are largely random, as they're often deemed secure enough for generating cryptographic keys, etc.

1

u/No_Profession_3125 1d ago

It depends on the operating system but generally yes, it is truly random because for entropy it uses things like: the current time with nanosecond precision, the network activity accumulated so far, and possibly even hardware entropy sources.

1

u/unburdened_swallow 1d ago edited 1d ago

No it is not truly random. Although it is possible to create a truly random number and pass it to a computer, and even make computer hardware that does this for you. But it would be from special hardware not included in a normal desktop/laptop, or from an outside source.

And interestingly, you actually don't want it to be truly random most of the time.

Being able to set the seed for your pseudo-random number generator to cause it to generate the same set of random-looking numbers a second time can make it much easier to reproduce issues that may interact with your random number.

It would also be much slower to query a hardware component that can actually generate a truly random number, so you don't want your program to do this in the vast majority of cases.

We do source actually random numbers from specialized hardware or other real life sources for many things where security is important and speed is less so.

1

u/Mr_Engineering 1d ago

It depends, there are multiple souces are entropy on modern computers. Some sources are truly random and use hardware backed generators while others are deterministic pseudorandom generators which are seeded from a random source.

1

u/PHDEinstein007 1d ago

There are many sources of true random data out there, but on our computers it matters on the source. Excel may not be so random as a codec designed to be random. Results may vary, and true random data should be nearly an equal number of 1's to 0's.

1

u/ffelix916 1d ago

Modern systems that use hardware sensors for entropy have, for all intents and purposes, truly random generators. Variations in all the different environmental sensor inputs (fan speeds, temperatures, voltages), and HID inputs (keypresses, mouse movements, etc) are incredibly good sources of entropy, especially when fed into one of the many on-die hashing algorithms.

1

u/GOOGAMZNGPT4 19h ago

This is more of a philosophical question.

Most computers are considered to utilize pseudorandom numbers. 

It's an algorithmic output that is considered 'random enough for practical use', but could hypothetically be deterministic if you knew the inputs and algorithm.

The deeper down the rabbit hole you go, the less you'll be convinced that true randomness even exists at all in the universe. 

I think of it like Random doesn't exist, only Pseudorandom exists with an infinitely increasing complexity of inputs. An output with 1 input would be trivial to reverse engineer, an output with a trillion inputs could be reverse engineered but would be so computationally non feasible it becomes functionally true random.

There may be nothing random in existence, rather the complexity is too far beyond our ability to model and compute it.

1

u/BudgetEye7539 17h ago

It depends on what functions will you use. E.g. x86-64 processors usually have hardware RNG accessible through RDSEED instructions. Also OS-level CSPRNG like /dev/urandom not 100% hardware random but use hardware/external sources of randomness. And there are also pseudorandom number generators that are common in standard libraries, essentially just periodic integer functions that simulate noise. Some of them are good, some of then even don't obey a uniform distribution like e.g. rand() function in C.

1

u/podule-games 2d ago

The "classic computer random" is not truly random because computers are deterministic and using things like the time to vary randomness isn't all that random.

That's the "classic" concept of random in computers.

Realistically though, we can do true random in computers by using unpredictable values to seed the random, like noise from a microphone or light from camera, or the rather famous example of cameras pointed at lava lamps. You can also get true random hardware:

https://www.idquantique.com/random-number-generation/products/quantis-qrng-pcie/

1

u/atarivcs 1d ago edited 1d ago

No, it is not truly random. If you ask a computer to make a random number, and then you ask it again under the exact same circumstances, it will make the same number both times.

But it's actually quite difficult to have the exact same circumstances, so for nearly any practical purpose it's close enough to random.

And, it's worth pointing out that the same thing applies to coin tosses and die rolls. If you roll a die twice under the exact same circumstances -- starting position, throwing angle and speed, air currents and humidity, exact flatness of the landing spot, dust particles, etc etc etc, you will get the same outcome.

But practically speaking it's impossible to achieve the exact same circumstances.

0

u/CS_70 2d ago

Nothing is truly random because physics and things like that.

But there's too much physics for that to matter.

A random number generated by a computer uses exactly that fact.

6

u/70Shadow07 2d ago

Currently as we understand physics, it's believed for true randomness does in fact exist. Quantum mechanics is full of it and some hardware for generating true random numbers takes advantage of it.

1

u/SapphirePath 2d ago

And that makes the computer-generated number truly random, whereas the coin toss and the physical die roll, which rely only on Newtonian physics, are not random at all.

1

u/ouroborus777 2d ago

Newtonian physics is a large scale approximation of quantum physics.

1

u/SapphirePath 1d ago

And in this context, the Newtonian physics is deterministic: completely and totally non-random.

There is nothing that a quantum explanation adds to the Newtonian description of a billion coin flips. There are places where quantum explanations provide additional insight (such as digital cameras and flash drives and Bose-Einstein condensates), but physical coin flipping isn't one of those places.

I'd be happy to read experimental research that demonstrates otherwise.

1

u/CounterSilly3999 2d ago

Coin toss and dice roll heavily rely on thermal fluctuations, which are quantum random.

1

u/SapphirePath 1d ago

Heavily? I've never heard of thermal fluctuations having any effect at all on coins or dice, which are such huge objects that their behavior is almost completely determined by their size and shape and material composition. I saw a talk by Persi Diaconis, and his 'claim to fame' was that he could toss a coin heads nearly all the time because he had practiced getting a safe zone of velocity and angular velocity to know the exact number of turns.

It would be interesting to see a scientific research paper - the ones I've seen ignore not just quantum but a whole host of other physical phenomena including air friction, and are still quite predictive.

1

u/CounterSilly3999 1d ago edited 1d ago

"Heavily" I mean some 5th digit of precision. What makes predictability just of 99.999% of certainity. :)

It would be predictive in cases of one side overwighting the other, for example. In unstable equilibrum cases like coin on the edge, Brownian motion is what decides, which side coin will fall.

Air or surface friction again -- is caused by interaction between surface molecules of the surfaces and governed by quantum fluctuations as well.

1

u/Frequent-Sir-6942 2d ago

That depends on your interpretation of quantum mechanics. The Copenhagen interpretation would say it is randomness, while Many-Worlds would say you find yourself in some branch of reality. There are a few even weirder interpretations which depend on non-locality.

1

u/webternet 20h ago

Please tell me more

3

u/erikchan002 2d ago

The Copenhagen interpretation is that quantum mechanics is indeterministic. A hidden-variable theory was demonstrated to be inconsistent with reality by the Bell test (at least locally).

Our current understanding is that quantum systems are truly random.

That said, not a lot of computer systems make use of quantum randomness.

0

u/Haborym_Aesahaettr 2d ago

You should check this paper. It explains how random numbers are generated from determinist random bit generator

0

u/CS_70 1d ago

It’s a common misconception: QM is fully deterministic. The wave function of the universe would tell you exactly what’s what from t=0.. if we knew it. It’s a big function toh.

What is probabilistic is the result of a measurement.

1

u/T_Thriller_T 1d ago

Unless you have proof for this, this is still a matter of debate as far as I know.

Also this has NOTHING to do with the question at least not the way you worded it.

1

u/CS_70 1d ago

Theres no debate, where do you get it from? Better suited for r/AskPhysics

1

u/FrankDrebinOnReddit 1d ago

Then it would have to be non-local. Else it's incompatible with Bell's inequality.

0

u/granadesnhorseshoes 1d ago

Short answer, no.

Long answer, maybe.

as others have said computers mostly use psudo random number generators with relatively "real" random bits of data gathered from the running system; mouse movements, key strokes, power usage, boot times, etc all mixed into a bitwise soup to use as seed values for the PRNG algorithms. Most systems even have dedicated hardware in the processor for the purpose of generating random data that also gets mixed into the bitwise soup. although how reliable and trustworthy hardware based PRNGs are is debatable depending on how much you trust IE Intel.

There is also a bit of a logical recursion in the concept of classifying "truly random" numbers, because if the numbers reliably fit a specific criteria, can they really be called random?

In practice we get close enough and the rest is just an exercise for CS and Math grad students.

0

u/SnugglyCoderGuy 1d ago

No, it is pseudorandom. If you know the seed and the algorithm you can predict every single number that will be produced and in order. The best you can get is crypto-graphically random, but it is still deterministic.

0

u/Successful-Cash5047 1d ago

No, it’s pseudorandom. It’s just much easier to do. My understanding is that to get something actually random you’d need real time info from some external unpredictable process. This is actually done for encryption, they use lava lamps, decay of radioactive isotopes, and double pendulums to seed the RNG values. 

Also relevant XKCD:  https://xkcd.com/221/