Do true random number generators exist for computer appliances and how do they work ?
In theory, yes. However, you’re not going to see one any time soon.
The most common proposed random number generator involves a geiger counter, and times the intervals between decay events. I’ve also heard talk of one that generates numbers based off of noise in a lobby or similar place.
The reason you won’t see this any time soon is because it’s overkill. Pseudorandom numbers are good enough for most applications, so there’s no point in doing something more.
Yes, they exist, although these are “true” in the sense of non-pseudorandom (I’m not going to get into a Great Debate about whether things are random at a quantum level!).
Generally thermal noise or radioactive decay is used as the source. All eletronic devices exhibit various modes of noise due to random electron movement. This can be amplified and used to generate random bits. Although it is simple in theory, in practice it can be tricky to eliminate ALL outside sources of electrical noise from biasing your numbers.
Here’s one such device that plugs into a PC: ZRANDOM - True Random Number Generator, from Westphal Electronics.
Radioactive decay devices are more immune to outside influences, but usually have a much lower bit rate (i.e. fewer random numbers per second). If you’d like a sampling of random bits, try the HotBits server, which uses a radiactive decay method, described here.
Arjuna34
Check out LavaRand:
http://lavarand.sgi.com/
It uses a collection of lava lamps sampled by digital camera to generate a seed for a random number generator. Their FAQ has some interesting info. The website it kind of goofy, but there’s some smart people behind it.
This scheme would be a little easier to assemble in your basement than a radioactive decay measurement, but it’s still a lot tougher than coding up a Blum-Blum-Shub algorithm, so most applications are going to stick with computer-generated pseudorandoms.
Please forgive me if this is a hijack, I suppose the OP has been answered, so this is a toss-up question.
Whenever someone asks if a number is “random” or not, I always wonder exactly what they mean. I’ve taken some probablity classes (at graduate level). I think I know what a “random experiment” is, and what a “random variable” is, but how can you look at a number, and say if it’s random or not? (eg. here’s a number for ya - 8, is that random enough for you?)
Let me try to guess. Let’s say you have a set of (potentially) random numbers. You also have a certain probablity distribution in mind (nobody ever mentions this part). You are really asking whether it is reasonable for the set you have to match the given probability distribution. Is that it? What do you say if the set matches some other probability distribution that you recognize. Do you now say it’s non-random? (probably not)
And what is meant by “pseudorandom”?
Don’t hold back on the mathematical jargon, at least on my account.
No particular number is “more” or “less” random than any other. When speaking of random numbers, you’re talking about the pattern of numbers generated from some sort of system. With mathematical functions that are pseudorandom number generators, after many numbers, patterns emerge.
This is why The Gummint does not like to use pseudorandom number generators for one-time cryptography keys, which most be truly random.
I forgot to add that in a truly random number generator, no matter how many numbers you generate, there will be no way to predict the next number.
So a generator makes truly random numbers if after n numbers it is impossible to guess number n+1, for any real value of n.
I don’t think “random” is very meaningful with respect to a single number. It’s more important when discussing series of numbers (e.g. generating 2048 bits which are randomly either zero or one for use as a cryptographic key).
To quote Bruce Schneier in Applied Cryptography, a pseudo-random sequence is one that “looks random”. It is non-periodic over the length of series needed and it passes statistical tests of randomness, it is unpredictable, and it cannot be reliably reproduced even with the same algorithm and input. He refers to more rigorous mathematical definitions, but this is the gist.
In general, the algorithm or method used to get the numbers is what determines whether it’s random or not. Anything done by a conventional computer program is going to be non-random because it is, by definition, deterministic. For example, the Blum-Blum-Shub algorithm is a cryptographically strong pseudo-random number generator which is used to generate psuedo-random bits with fairly good confidence that someone could not crack the algorithm and anticipate unknown parts of the series. However, it’s not truly random, and for any application you have to judge how much randomness you really need.
What exactly are these statistical tests of randomness? I’ve always wondered that.
Fair enough, but it seems to me that you just described a “random experiment” or “process”. If that’s the only semantic that we’re talking about, then I have no more to say. This is the same thing that micco is talking about:
If you know your method is random, then, of course, you get random numbers. I’m trying to understand whether people can determine whether they know that a sequence is random just by looking at the sequence. I suspect nobody can.
Even a 2048 bit string of bits is a single (binary) number. Would you say that if your Blum-Blum-whatever (I confess ignorance on cryptography) algorithm punched out 2048 zeros in a row, that that number is “not random”?
Which seems to be the crux of the problem. What is the proper way to measure “randomness”? I’d agree, that if I crack your algorithm, then it becomes deterministic. But how can I really tell if I have your algorithm? How many numbers do I have to guess right? One? Five? A hundred?
I would say the common definition of “random” implies an equal probability distribution. All numbers come up equally given enough time. It’s assumed so it’s not stated.
Ultrafilter wrote:
Layman here, so I don’t know exactly, but I would like to know how close I was, twenty years ago. I was talking with Dad one day about random numbers, and writing my own generator for kicks. He, of course, thought that’d be a great little snippet of education for me, and made some suggestions on testing any generator I came up with.
What I came up with, which seemed to work well, was creating a histogram, and visually inspecting it for “flatness” periodically. Generate random numbers between, say, 1 and 100, and plot them on a histogram on the screen. Reset every umpty-ump thousand, or million, numbers. If, at any point in time, the histogram isn’t “flat” (every number showing up about equally), then you know there are problems. If, for example, there are consistently twice as many 67s being generated as all other numbers, it isn’t quite random.
One of my earliest attempts at a generator created a plot which quickly told me how bad it was - only multiples of three were being generated. Spike - null - null - spike - null - null - spike - null - null, etc.
Of course, if your RNG isn’t supposed to be flat (such as the total of two dice, which should display a classic bell curve histogram), you’d have to take that into account. I’m sure someone of a statistical mind will come along soon to speak of mystical things like “chi square” tests and the like, which, I think, are methods whereby what I refer to as “flatness” is actually quantified, and will give you a value represeting the odds that, say, twice as many 67s are generated vs. any other number. If the odds are too high against, it isn’t random.
As an aside, I have also used the “flatness” method to determine whether or not a slew of data-compression schemes were “doing their best” at compressing the data. After all, if a compressed file doesn’t look random, then there may be patterns left in the data which could be further compressed.
I think the Kolmogorov notion applies here. Basically, the “randomness” of a string is the amount of information contained therein, which is measured by the length of the shortest program that can produce it. So a truly random sequence of numbers (call it s) couldn’t be produced by a program shorter than “print s”.
Whoops. Two dice should form a pyramid curve - twice as many 3s as 2s, 3 times as many 4s as 2s, 6 times as many 7s as 2s, then back down to 12s and 2s having similar numbers. A bell-curve shape shows up when you add three dice together.
I think you missed something there. The way it was taught to me, the whole point of pseudorandom algorithms is that you can supply the same seed and generate the exact same sequence of numbers. Computers are deterministic, given the same inputs to the same algorithms, they will arrive at the same results every time. This is essential for debugging, and also the weakness of pseudorandomness.
Well, according to this site, 17 is the ‘least random number’ 
(BTW - the whole Jargon Dictionary is a great read for anyone involved with computers)
Regarding the defintion of randomness, here is a thread that discusses whether the digits of pi can be considered random or not - apparently, even though it has almost been proved that pi is ‘normal’ (each digit occurs with equal frequency in its expansion), the digits cannot be considered random, since there are well-known algorithms for computing the nth digit [aside - how to make a superscript (nth) in vB code?]
Search for ‘pi digits random’ in the SD search engine for more threads discussing this.
The tags you want are [**sup] and [/**sup]. There’s a sub tag for subscripts, too.
Yes, and if you foolishly use the computers tick count as a random seed during boot you’ll get the same seed (msec since startup) over and over and generate the same series of pseudorandoms every time you boot 
The seed completely specifies the output sequence for pseudorandom generators.
Hmmm, except that most computers don’t take exactly the same number of milliseconds to boot up every time; in theory they should, but in practice, things like spinning the hard drives up to speed and even little things like temperature variations will make a difference.
not that I’m saying that it would be a good idea to do it that way though.
I have an idea; the lava lamps thing was pretty interesting, but can’t the same kind of real-noise effect be got from the universal background radiation that causes snow on an untuned TV screen? (then it could theoretically be done using a TV card in your PC).
Statistical tests like Chi-square and Kolmogorov-Smirnov can be used to get measures of randomness. Knuth’s second volume, The Art of Computer Programming, Seminumerical Algorithms has a whole chapter on random number generation and testing, so I’ll defer to that rather than citing a bunch of math. It’s pretty much the bible for algorithms, so you should be able to find it in any good library.