Random number generator

A random number generator is a computational or physical device designed to generate a sequence of elements (usually numbers), such that the sequence can be used as a random one. Methods for generating random results 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. The usual tests of such sequences for randomness attempt to ensure that they do not have any (or less rigorously, no easily discernable) patterns.

"True" random numbers vs. pseudo-random numbers

How to destinguish a "true" random number from something else 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 arithmetic methods to produce random numbers is in a state of sin", thus neatly summarizing the situation.

However, under some circumstances, carefully chosen pseudo-random number generators can be used instead of true random numbers in some applications. Rigorous numerical analysis is often needed to have confidence

Random numbers in computing

Most computer programming languages include functions (or library routines) 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 necessarily deterministic, and therefore not truly random; furthermore, they too often have poor statistical properties and sometimes will repeat patterns after only tens of thousands of trials. They are sometimes initialized using a computer's real time clock, which may provide enough randomness for such things as game play, but they should never be used for many purposes, especially cryptographic applications. Higher quality random number sources are available on most operating systems; see, for example /dev/random on Linux and Mac OS-X, or this note for Microsoft Windows.

Generating random numbers from physical processes

There is general agreement that, if there are such things as "true" random numbers, they are most 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 which are aspects of quantum mechanics. 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.

To provide a degree of randomness intermeidate between specialized hardware on the one hand and algorithmic generation (without the expense of a hardware implementation) on the other, some security related computer software requires the user to input a lengthy string of mouse movements, and/or keyboard input, or both as 'randomly' as can be managed.

Post-processing and statistical checks

Even given sources of plausible random numbers (pehraps from a quantum mechanically based hardware generator), obtaining numbers which are completely unpredictable and unbiased is very difficult. Since random number generators are designed to be unpredictable, it is difficult to ensure that they are being predictably unpredictable. For example, many hardware random number generators generate sequences of numbers around certain areas rather than having uniform distribution across all possibilities. In addition, behavior of these generators often changes with temperature, power supply voltage, the age of the device, or other outside interference. And 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 generally subjected to statistical tests before use (to ensure that the underlying source is still working), and then post-processed to improve their statistical properties. Especially paranoid users may test them again, to ensure there are no detectable patterns.

Random numbers uniformly distributed between 0 and 1 can be used to generate random numbers of any desired distribution by passing them through the inverse cumulative distribution function of the desired distribution. To generate a pair of independent standard normally distributed random numbers (x, y), one may first generate the polar coordinates (r, θ), where r~χ₂² and θ~UNIFORM(0,2π).

Also, when using random numbers, care must be taken to consider 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, combining their outputs (using, for example, XOR) will provide a combined RNG 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 reflect 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

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 making 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 may, and usually does, leave larger gaps.

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.

Cryptographically Secure Random number on Windows without using CryptoAPI from MSDN
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)

Randomness | Information theory

Zufallszahlengenerator | Générateur de nombres aléatoires | Toevalsgenerator | Generator liczb losowych

Gourt Home::Gourt :: Random number generator