Random number generator: Encyclopedia - Random number generator

Random number generator

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.

Random number generator - True random numbers vs. pseudo-random numbers

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".

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 usually needed to justify 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 number generator - Generating random numbers from physical processes

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 relying on quantum mechanical processes have the advantage that the sequences they produce are completely unpredictable, if we assume that current theories of quantum physics are correct.

Random number generator - 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 generate random numbers which tend to get focused in certain areas instead of being distributed uniformly, and their behavior may change with temperature, with voltage, with the age of the device, or with 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 both, and yet others 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.

Random number generator - Uses of random numbers

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.

Random number generator - 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

Adapted from the Wikipedia article "Random number generator", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki