How could a random generator be implemented?
I'm not speaking about the invocation of a language mathRandom() method, but the implementation of the routines that lead to generate numbers totally random.
-
1I'd venture to say that true randomness is not presently possible.– DynamicCommented Dec 17, 2012 at 22:49
-
@Dynamic I think the same think, however I have always invoked random function when needed, but I haven't idea of how a random method should be implemented.– AsgardCommented Dec 17, 2012 at 22:52
-
8"totally random" is a very deep rabbit hole.– whatsisnameCommented Dec 17, 2012 at 23:18
-
@Dynamic: It is actually trivial to get a sequence indistinguishable from truly random data, as long as you look to the outside world with hardware support. Atomic and Subatomic physics, (Atomic decay, photon hitting sensors type events) is (to the extend of current science theory) truly random and easy to measure. Thermodynamics on a large scale is so chaotic that we can consider it random when we inspect at the macro system on the the micro scale etc. Noise from a digital camera sensor is a good example.....– mattnzCommented Dec 18, 2012 at 3:14
Add a comment
|
5 Answers
The key for a truly random number is random data source. Sometimes this is information such as delays in keyboard events or network events. Where high quality random data is desired, it may be radioactive decay. SGI implemented lavarand which drew its seed for a random number generator from a digitized image of a lava lamp. This was sufficient for being considered a random number generator.
Outside of truely random data, one can work with a deterministic but chaotic system. For example, the mersenne twister. In these situations, one seeds the generator with a number and then runs it forward to get pseudo-random numbers. These are sufficient for games and the like where it isn't critical if someone can determine the seed (and the next number in the sequence).
Consider reading patent 5,732,138 and http://www.lavarnd.org/ for the implementation details on how to make a number.
-
1+1 I would consider different data sources like weather measurements for your seed. wiki.cdyne.com/?title=CDYNE_Weather Commented Dec 18, 2012 at 2:15
-
1@emeraldcode.com the challenge with weather measurements is they are not completely random. There is an entire field about predicting the weather. Temperature tends to go up then down over the course of a day. Winter is colder than summer. The hotbits system uses the randomness of timing two decay events which are unpredictable (measure time from event 1 to event 2, and the time from event 3 to event 4 - if 1:2 == 3:4, toss out the data. If 1:2 < 3:4, the random bit is 0. If 1:2 > 3:4, the random bit is 1.– user40980Commented Dec 18, 2012 at 17:52
-
I'm talking about wind speed, barometric pressure, temperature, humidity, etc. You can take a sample of measurements and have a hard time arguing against randomness in that regard. Also, temperature alone taken at enough accuracy is very random. Commented Dec 18, 2012 at 23:42
What kind of random are you talking about?
There are two main properties that define random in mathematical sense: the first is unpredictability and the second is uniform distribution.
If you're talking about the first, it's generally almost impossible to generate it entirely within software (and to do it properly). There are some ways, such as gathering entropy from human interface devices, e.g. /dev/random in Linux, but we generate a fairly low level of entropy to be useful. Others have already pointed some hardware implementations. They all have roots deep within physics theory (like our belief that the precise moment a photon will hit a detector is truly random). There are some software algorithms for this, like Blum-Blum-Shub. In general, don't write a PRNG if you need unpredictability, but rather use an established one. This goes especially with crypto.
The other important property of random functions is actually fairly easy to satisfy. There are many examples of this, like the RNG behind RC4, Linear Feedback Shift Registers (this was actually used for crypto, too, once upon a time, but was found insufficiently secure), etc. Even the standard C library rand() will probably work fine for this purpose.
Most important: Make sure you know which of the two properties is fundamental to your need. Unpredictable PRNGs are uniformly distributed, too, but the other way around is not true. Also, if you are exposing the randomness inside an 'engine' of some sort (like a game engine), make sure people cannot game the system, because you might be surprised how easy that actually is. For example, CSS (the DVD encryption algorithm) used 2 LSFRs for cryptography purposes and was broken fairly easy.
First, you can't generate truly random numbers in software. There are a ton of different algorithms that let you generate pseudo-random numbers. Depending on why you need pseudo-random numbers (i.e. if you are using them in cryptography the requirements are much different), you would generally use something like the random number generator in the GNU scientific library (which, of course, you can implement in whatever language you prefer).
answered Dec 17, 2012 at 22:55
Hardware. You need to connect to hardware that can gather entropy from... wherever. Read the static from a radio, put a webcamera on a lavalamp, or have the user type gibberish or play with the mouse. Without some contact with the real world, generating true randomness is impossible. It's an important area of study, and a lot of work has been put into it. I doubt you're going to be blazing any new trails, so you really ought to stand on the shoulders of giants and start reading wikipedia entries.
"The generation of random numbers is too important to be left to chance."
-Robert R. Coveyou
EDIT
So I've learned that the hardware you want is in fact just a CMOS chip. The sort in cheap cameras. Just keep it in darkness, set the sensitivity way up, and apparently the minute variances it observes has roots in quantum mechanics, which is where we derive our entropy in real life.
Last time I looked, which was a LOOOOONG time ago, the canonical reference on implementation of pseudorandom number generators (PRNG) is Knuth, Vol. 2, "Seminumerical Algorithms".
Don't even THINK about trying to implement your own PRNG until you've at least looked through Knuth.
answered Dec 18, 2012 at 4:51
