So how? I can’t imagine the computer has some sort of inbuilt formula in it for producing random numbers, since it would have to get some numbers to start with and to input to the formula; then again, the starting numbers would have to be random, and the problem is not solved but only delayed.
One very popular online casino advertises on ist homepages mentioning that they use an algorithm called MD5 for their random sequences which is said to be very trustworthy. What’s the Straight Dope on this?
oh where to begin.
First of, computers can not generate truly random numbers, they can generate seemingly random psuedorandom numbers.
It depends on what program/library the programmer who wrote the program youre using on how it generates the random numbers. They are typically based on the system clock, mouse movements, keystrokes, any combonation and modification of coninually changing events.
The MD5 algorithm you refer to is not explicity an random number generator but a one way hashing algorithm. Its main use is in cryptography, but thats a different much longer explanation. A one way hash will take a certain amount of data in, and return seemignly different data typically of a much shorter length. It is nearly impossible to take a hashed piece of data and figure out what it started as. Entering the exact same data in will result in the same data coming out, but if that incoming data is modified by just one BIT, the outcoming hash will be entirely different. By making minute changes to the incoming data, drastic, apparently random changes will come out. The slight variations become large ones and the large variations lead to seemignly random numbers.
I used “Applied Cryptography” by Bruce Schneier as referece for this post.
Basic compilers have only 1 random number generator function. If you use a stat software package like SAS or SPSS they give you multiple functions that use different techniques to get random numbers.
True random number generators are nearly if not completely impossible.
Watching a show on cryptography are cryptanalyst stated that any system for generating numbers is based on some set of rules (or instructions). By default that means that they can never be truly random.
There are a number of ways to generate random and pseudorandom numbers. Most computers generate pseudorandom numbers: they take a “seed” number (often, the time of day, or some other frequently-changing number like the number of seconds the computer has been running), and then shove it into a mathematical formula that “scrambles” the digits around in a way that, while entirely predictable, will not repeat over a very long number of iterations so as to “appear” to be random. However, such numbers are not random: they are perfectly predictable. They’re good enough for games, but not good enough for encryption. The MD5 hash function (normally used in encryption systems) is computationally very hard to “reverse” so it makes a good pseudorandom number generator.
Some systems, including all recent Linux systems, can generate true random numbers by collecting “entropy” from the hardware environment. There are a lot of things in a computer that happen because of events that take place outside of the computer: the mouse moves, the keyboard is typed on, network packets arrive, and so forth. This activity is called “environmental noise” and is a good source of randomicity. The operating system kernel uses the times that elapse between these events occur to generate “entropy” which is then used to generate truly random numbers. This sort of randomicity is strong enough for encryption (or in fact for any known purpose). You might find the comments at the top of the source code for the /dev/random driver illuminating. (Or maybe not. This is pretty geeky stuff.)
That was an excellent summary KellyM. Of course even system entropy is not a perfect source for random numbers since key stroked and network packets themselves have predictable timing patterns It is said that numbers gotten from these methods are more random than simple pseudorandom number functions, in that it is more difficult to find patterns in them (and the patterns perhaps have greater lengths) but they are far from perfectly random. In a perfectly random sequence, there would be no repeatable patterns in an infinately long period.
It’s impossible to test an infininately long period of course, so the question arises if randomness even exists in the Universe. (Are there hidden patterns in Pi? Who knows? Cue spooky music.)
One way to get excellent numbers that appear to be quite random indeed is natural entropy. One of the best sources being the time between radioactive decay events. The National Security Agency has used a chunk of radioactive something-or-other to generate One-Time Pads in the past.
Don’t know if this is true, but it sounds reasonable…
At online casino based most of it’s poker games on shuffling algorithm, or course based on “random” numbers. Unfortunately, the algorithm kicked off at midnight every night, and the random number was based on the system clock. So the decks got shuffled the same way to start every day. And some bright punk figured it out, logged in every day at midnight and won the first hand of the night for big bucks.
This has been covered pretty well, but I thought I’d provide a pointer to the RFC on the subject: http://www.ietf.org/rfc/rfc1750.txt
This should give you more information than you ever wanted about how random numbers can be generated, why is so hard to generate numbers that are random enough, why they are important, and why, if you ask a programmer about this, there is a good chance that they will keep talking until your eyes glaze over.
slight hijack
If pi is “normal” (which, as far as I know, it is), then it contains every possible (finite) pattern at some point in its expansion. The existence of the patterns is undoubted; the question is merely one of where they are. However, finding a pattern would be of no cosmic import, but merely the discovery of a bit of amusing mathematical trivia.
The key to effective randomicity is that there be no way for someone to predict the next randomly generated unit, even if the predictor has complete knowledge of the mechanism by which the random numbers are generated and all of the generator’s past random numbers. It’s quite possible for this to hold even if the source of randomicity is not “perfectly random” as long as the nature of its deviation from perfectly randomness is not known to the predictor. (This is why mouse and keyboard interrupts usually work well: while there may well be a pattern, it’s not at all likely that a predictor would know what it is.) Radioactive decay, as others have noted, appears to be pretty damn opaque on this point: if there’s a deviation from perfect randomness, nobody knows what it is.
How random is white noise?
I think in a Tom Clancy book, I read they used white noise from atmospheric RF emmissions to generate the random numbers for one-time padding encryption.
I would guess that this is truly random.