Random number generator
From Free net encyclopedia
A random number generator is a computational or physical device designed to generate a sequence of numbers that does not have any easily discernable pattern, so that the sequence can be treated as being random. Random number generators have existed since ancient times, in the form of dice and coin flipping, the shuffling of playing cards, the use of yarrow stalks in the I Ching, and many other methods.
Contents |
"True" random numbers vs. pseudo-random numbers
Template:Main What constitutes a "true" random number is often difficult to decide, since the concept of randomness is itself somewhat difficult to define. What is universally agreed is that any "random number generator" based solely on deterministic computation cannot be regarded as a "true" random number generator, since its output is inherently predictable. John von Neumann once famously said "Anyone who uses software to produce random numbers is in a state of sin" (some sources say "arithmetic methods" instead of "software").
However, under some circumstances, carefully chosen pseudo-random number generators can be used instead of true random numbers for some applications. Rigorous numerical analysis is often needed to have confidence their use is acceptable in these applications.
In other circumstances, particularly for security applications, the use of pseudo-random numbers instead of true random numbers can completely compromise the application they are being used for.
Random numbers in computing
Most computer programming languages include functions that purport to be random number generators. They are usually designed to provide a floating point number uniformly distributed between 0 and 1.
Such functions are deterministic, and therefore not truly random; furthermore, they often have poor statistical properties and sometimes will repeat patterns after tens of thousands of trials. They are sometimes initialized using the computer's real time clock, which may provide enough randomness for purposes such as game play, but they should never be used for cryptographic purposes.
To get a random digit from the random function that is an integer that lies between the value A and B where B > A, and where the function random() provides a decimalised value between 0 and 1, and the (int) modifier truncates the number to the nearest integer below the value (e.g. 1.4 goes to 1, 3.9 goes to 3);
int randBetween(int A,int B){
double r = random();
r *= (B - A);
r += A;
return (int)r;
}
or to simplify;
int randBetween(int A,int B){
return ((int)((B-A)*random()))+A;
}
Generating random numbers from physical processes
Template:Main There is a general consensus that if there are such things as "true" random numbers, they are likely to be found by looking at physical processes which are, as far as we know, unpredictable.
A physical random number generator is based on an essentially random atomic or subatomic physical phenomenon. Examples of such phenomena include radioactive decay, thermal noise, and shot noise.
Physical random number generators that rely on quantum mechanical processes have the advantage that the sequences they produce are completely unpredictable.
Post-processing and statistical checks
Even given sources of plausible random numbers, obtaining numbers which are completely unpredictable and unbiased is a very difficult task. Since random number generators are inherently designed to be unpredictable, it is difficult to ensure that they are being predictably unpredictable. For example, many hardware random number generators tend to generate sequences of numbers that are focused in certain areas rather than having uniform distribution, and their behavior may change with temperature, voltage, the age of the device, or other outside interference. A software bug in a pseudo-random number routine, or a hardware bug in the hardware it runs on, may be similarly difficult to detect.
For these reasons, random numbers are typically subjected to statistical tests before use (to ensure that the underlying source is still working), and then post-processed to improve their statistical properties.
Also, when using random numbers, we must take into account whether they include or exclude their upper and lower bounds. Some 0 to 1 RNGs include 0 but exclude 1, while others include or exclude both.
If you have access to many independent RNGs, XORing their results will provide a combined RNG that is at least as good as the best RNG you have access to. More details about uncorrelated near random bit streams.
Computational and hardware random number generators are commonly combined to obtain the benefits of both kinds. Computational random number generators can typically generate pseudo-random numbers much faster than physical generators can generate true randomness.
- See also: Statistical randomness
Uses of random numbers
Template:Main Random number generators have several important applications in gambling, statistical sampling, computer simulation, etc.
Note that, in general, in applications where human fraud or adversaries exist, hardware-generated numbers should be used in preference to pseudo-random number generators.
Low-discrepancy sequences as an alternative
Some computations that make use of a random number generator can be summarized as the computation of a total or average value, such as the computation of integrals by the Monte Carlo method. For such problems, it may be possible to find a more accurate solution by the use of so-called low-discrepancy sequences, also called quasirandom numbers. Such sequences have a definite pattern that fills in gaps evenly, qualitatively speaking; a truly random sequence usually leaves larger gaps.
See also
- Hardware random number generator
- Pseudorandom number generator
- Random number generator attack
- Randomization
External links
Random numbers available over the internet and from parties not specifically known to and trusted by the user should not be used cryptographically.
- Random.org - generate random bitmaps, flip virtual coins etc. (random numbers generated from atmospheric noise from a radio)
- HotBits: Genuine Random Numbers (random numbers generated from radioactive decays)
- LavaRnd demonstration (random numbers generated from a webcam CCD chip)
- RandomNumbers.info (random numbers generated by exploiting elementary quantum optics process)
- KenoRND() (random numbers generated from results of live keno at real casinos)
- www.true-random.com (random numbers generated from digital noise and based on the central limit theorem)de:Zufallszahlengenerator
fr:Générateur de nombres aléatoires nl:Toevalsgenerator pl:Generator liczb losowych