Random number generation

• Goodness is treated inadequately
• Overlap with more specific references are too scarce or too extravagant
• Hardware and software implementation is very poor

A random number generator, sometimes shortened to random number generator refers to a process that produces a sequence of random numbers. The region from which the random numbers are generated, depends on the particular random number generator. A basic distinction between non- deterministic and deterministic random number generators. Non- deterministically a random number generator is when he provides even for the same initial conditions different values. Since the implementation of a software procedure works always deterministic, an external, such as a physical, process must be included for the realization of a non- deterministic random number generator. A deterministic random number generator always delivers with the same initial conditions, however, the same sequence of numbers. Often, both forms are combined into a hybrid generator.

Random numbers are required, among others, in various statistical methods, such as in selecting a random sample from a population, in the distribution of animals in different experimental groups ( randomization) or at the Monte - Carlo simulation. Other typical application areas are ( computer, happiness ) games and various cryptographic techniques.

• 2.1 quality of a pseudo-random number generator
• 2.2 Nicht-periodischer/unendlicher generator
• 2.3 Software Technical realizations
• 2.4 Hardware Technical realizations

Nondeterministic random number generators

A physical random number generator

A physical random number generator is used to generate random numbers and used for physical processes.

Here, for example, the pulse variations of electronic circuits (e.g., thermal noise of a resistor ), or radioactive decay processes are exploited. In general, all natural sources may be used that are based on physical effects and provide a very high quality, but also other asynchronous sources, such as:

• Atmospheric noise ( like a non- tuned radio )
• CCD sensor noise ( with a bad (eg mobile phone ) camera photograph in a dark room and derive random numbers )
• Fluctuation of the actual duration of a to a timer ( ' timer ' ) measured period of time.

However, physical random number generators are not considered fast since independence and equal distribution of the random numbers generated can only be achieved by sufficiently large distances in the observation of physical processes or scavenging. But this is only a question of technology used, because random processes such as thermal noise have cutoff frequencies of many terahertz.

Also the reproducibility of the results is in principle not possible because the random numbers produced are truly random, such as the lottery draw. Thus, the random numbers produced are aperiodic, i.e., non-repetitive sequence of random numbers ( in principle, that is, when the generator is running for long enough ) to infinity.

For example, measure the number of radioactive decays in a given time a Geiger counter. One uses the fact that radioactive isotopes for a purely random period of time decay into the daughter element or isotope. The period of time but in the same isotope of the same more mean value ( the so-called mean lifetime that is related to the half-life of about a factor of 1/ln (2) ). Since the radioactive decay almost always runs regardless of ambient conditions, this process can provide random numbers of high quality.

In addition, noise generators can be used as random number generators.

A method for constructing random number generators in digital circuits is the use of metastability in edge-triggered flip-flops.

Good physical method for generating random numbers are also rolling the dice and the draw of lottery numbers, with their typical machines. (See also: lottery draw ).

In physical random number generators, there are, however, the problem of aging. For example, Geiger- Müller counter tubes a lifetime of typically one billion pulses and are also dependent on temperature, magnetic fields and the supply voltage. It must also at Geiger counters, the pulse rate will be " significantly higher" than the clock frequency at which the pulses are read. A solution to this problem is to take many more or less good random number generators, and to use only these random numbers, the last bit in order to form the modulo two sum ​​. According to the central limit theorem of statistics is thus obtained even with bad random number generators perfectly random random bits, if you have only a sufficient number of random number generators.

Hardware Technical Components

• Installation of a radioactive source whose radiation is measured and serves as the basis of the random number generator.
• One is the realization by the noise generator.

Quasi- Random Events

There the system time is determined, for example, in a user action occurs. In this way, random numbers generated usually have a low quality, but can be used as starting value for deterministic methods use.

Deterministic Random Number Generators

Deterministic random number generators produce pseudo-random numbers and are therefore usually called pseudo-random number generators (English pseudo- random number generator, PRNG ). They generate a sequence of numbers that might look random, but it is not, since it is calculated by a deterministic algorithm. Such pseudo-random numbers are much easier to produce by computers and are available in virtually all languages.

Each time you start the calculation with the same initial value (English seed, seed ) is produced the same result, which is why these pseudo random numbers deterministically generated can be reproduced with reasonably accurate documentation later. This property of reproducibility is important for the recognition of scientific experiments.

Rhymes in children's games also provide a kind of deterministic random number generators dar.

Quality of a pseudo-random number generator

The numbers generated are characterized by statistical properties. This includes the distribution generated (eg, normal distribution, uniform distribution, exponential distribution, etc.) or the independence of consecutive numbers. How well the generated numbers correspond to the statistical requirements, the quality of a pseudo-random number generator determined.

The example of a pseudo-random number generator that can output only the numbers 0 and 1 (eg simulated coin toss ), you can make it clear that only the same frequency of both results is not sufficient, since about the sequence 0, 1, 0, 1, 0, 1, 0, 1, ... intuitively not randomly appear. If possible, the possible pairs of consecutive results with the expected frequencies occur, even if possible, triples, quadruples, etc. These considerations lead to the Spektraltest.

A very simple criterion is the period length, which should be as long as possible in relation to the range of values. This is the case with the Mersenne Twister to a particularly great extent. A simple linear congruential generator can, however, the range of values ​​per period, at best, run through once; this should be reversed seen as a minimum requirement and can be checked by a simple criterion ( set of Knuth ).

More quality tests based on the chi -square test, the Kolmogorov -Smirnov test and Others

Knuth lists numerous other tests, so the "serial test", the gap test, the poker test, the coupon collector's test, the permutation test, the run test, the maximum of - test and the collision test. It happens quite possible that a generator very fares well in several tests, but fails in another. For some applications, such as simulations, which are near the respective test conditions, such a generator is then suitable.

Particularly stringent requirements are placed on cryptographically secure random number generators.

Nicht-periodischer/unendlicher generator

Take the fractional part of a root of an integer as random numbers. Care must be taken, of course, that the resulting root is an irrational number. Classically, one can use instead of the circle number. Although in this case it is guaranteed that the sequence of numbers generated is not periodic, but in these examples do not even known whether it is evenly distributed, not to mention further statistical tests throughout (see Normal number).

Software Technical realizations

• Arithmetic random number generators based on the arithmetic. Irrational numbers such or can be used as random number generators by utilizing the fractional part of any multiples as random numbers. Disadvantage of the method is that irrational numbers can be represented as approximate values ​​within the computational accuracy.
• Recursive arithmetic random number generator: These methods are based on the calculation of a new random number from one or more of the preceding figures. The number of newly generated is stored and is received by reopening the random number generator in the calculation. At the very first call to the random number generator must be an arbitrarily chosen starting value, the seed (usually engl. Seed ) are used. congruential linear congruential multiplicative congruential
• Mixed linear congruential

Hardware Technical realizations

• Shift register with feedback linear shift register
• Nonlinear shift register

Hybrid generators

In practice, one often uses arithmetic random number generators, which are a hybrid. Calculate pseudo-random numbers, use for this, however - if necessary - a truly random seed value. However, the entropy of the generated random number can not be larger than the starting value.

In practice, one finds such hybrid random number generators under Unix-like operating systems such as Linux and BSD / dev / random and / dev / urandom. This show virtually no statistical abnormalities. However, its initialization is effected in most cases with the above-described methods, but by evaluating the temporal distance of hardware events ( keystrokes, network traffic, and the like), which may also be considered to be random.

In the simplest case, a pseudo-random number generator is simply removed, which is started occasionally with a new true random number as the start value again.