Random number generator

A random number generator , or random generator for short , is a process that generates a sequence of random numbers . The range from which the random numbers are generated depends on the special random number generator.

A basic distinction is made between non-deterministic and deterministic random number generators. A random number generator is non-deterministic if it delivers different values even with the same starting conditions. Since the implementation of a software procedure usually works deterministically, an external (for example physical) process must be included in order to implement a non-deterministic random number generator. A deterministic random number generator, on the other hand, always delivers the same sequence of numbers with the same starting conditions. Often both forms are combined to form a hybrid generator .

Random numbers are required, among other things, for various statistical methods , e.g. B. when selecting a sample from a population , when distributing test animals to different test groups ( randomization ) or when performing a Monte Carlo simulation . Other typical application areas include ( computer , happiness ) games and various cryptographic methods.

Non-deterministic random number generators

Physical random number generator

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

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

Atmospheric noise (like analog radio that is not tuned to a station)
CCD sensor noise (take a photo with a bad (e.g. old mobile phone) camera in a dark room and derive random numbers from it)
Variation in the actual duration of a period of time measured with a timer (“timer”).
Voltage fluctuations on a Zener diode .

However, physical random number generators are not considered to be fast, since an independence and uniform distribution of the generated random numbers can only be achieved by sufficiently large distances when observing the physical processes or interception methods. However, this is only a question of the technology used, because random processes such as thermal noise have limit frequencies of many terahertz .

In principle, reproducibility of the results is also not possible, as the random numbers produced are genuinely random (like the lottery numbers). As a result, the random numbers produced are aperiodic , i.e. H. the non-repeating sequence of random numbers is (in principle, i.e. if the generator runs long enough) infinite .

For example, a Geiger counter can measure the number of radioactive decays in a certain period of time. One uses the fact that a radioactive nuclide decays into its daughter nuclide after a purely random time . The time span always has the same mean value for the same nuclide (the so-called mean life, which is related to the half-life via the factor .) Since the radioactive decay always takes place independently of environmental conditions, this process can deliver high-quality random numbers. ${\ textstyle {\ frac {1} {ln (2)}}}$

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

One method of building random number generators in digital circuits is to utilize the metastability of edge - triggered flip-flops .

Good physical methods for generating random numbers are also rolling the dice and drawing lottery numbers with the typical machines. Random draws in relatively quick succession were implemented in electromechanical gaming machines , based on cam disks with eccentric wheels and a switching time variator.

However, the problem of aging exists with physical random number generators. For example, Geiger-Müller counter tubes typically have a service life of one billion pulses and are also dependent on temperature, magnetic fields and the supply voltage. In addition, the pulse rate of Geiger counters must be “significantly higher” than the clock frequency with which the pulses are read. One solution to this problem is to use a large number of (more or less good) random number generators, with only the last bit of the random numbers generated being used to form the modulo-two sum. According to the central limit theorem of statistics, this means that perfectly random bits are obtained even with poor random number generators (provided that a sufficient number of random number generators are used).

Quasi-random events

For example, the system time is determined within which a user action occurs. Random numbers generated in this way are usually of poor quality, but can be used as starting values for deterministic processes.

Deterministic random number generators

Deterministic Random Number Generators generate pseudo-random numbers and are therefore generally pseudo-random number generators called (Engl. Pseudo random number generator , PRNG ). They generate a sequence of numbers that looks random , but is not because it is calculated by a deterministic algorithm . Such pseudo-random numbers are much easier to generate by computers and are available in practically all high-level programming languages .

(Engl. Each time the calculation with the same initial value seed , d. E. Seed ), the same sequence is generated, so these pseudo random numbers generated deterministically later in sufficiently accurate documentation reproduced can be. This property of reproducibility is important for the recognition of scientific experiments .

Counting rhymes in children's games are also a kind of deterministic random number generator.

Quality of a random number generator

The numbers generated can be checked by statistical tests. This includes the generated distribution (e.g. normal distribution , uniform distribution , exponential distribution , etc.) or the independence of consecutive numbers. The quality of a random number generator determines how well the generated numbers meet the statistical requirements.

Using the example of a random number generator that can only output the numbers 0 and 1 (e.g. simulated coin toss), it can be made clear that the same frequency of both results alone is not sufficient, as the sequence 0, 1, 0, 1, 0, 1, 0, 1, ... intuitively does not seem random. In the optimal case, all possible pairs of successive results with the expected frequencies should also occur, and if possible also triples, quadruples, etc. These considerations lead to the spectral test .

A very simple quality criterion is the period length, which should be as long as possible in relation to the value range. This is particularly the case with the Mersenne Twister . A simple linear congruence generator , on the other hand, can at best run through the range of values once per period; conversely, this should be seen as a minimum requirement and can be checked by a simple criterion ( Knuth's theorem ).

Further quality tests are based on the chi-square test , the Kolmogorow-Smirnow test and the like. a.

Knuth lists numerous other tests, such as the "serial test", the gap test, the poker test, the coupon collector test, the permutation test, the run test, the maximum-off test and the collision test. Test. It happens that one generator does very well on several tests but fails on another. Such a generator is then unsuitable for some applications, such as simulations, which are close to the corresponding test conditions. ${\ displaystyle t}$

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

Non-periodic / infinite generator

Consider the decimal places of the square root of a natural number as random numbers (here you must of course make sure that the resulting root is an irrational number ). Classically, you can use the circle number instead. It is guaranteed here that the sequence of numbers generated is not periodic; however, in these examples it is not even known whether it is evenly distributed (not to mention more extensive statistical tests; see normal number ). ${\ displaystyle {\ sqrt {n}}}$ ${\ displaystyle \ pi}$

Software implementation

Arithmetic random number generators are based on arithmetic . Irrational numbers like or can be used as random number generators by using the fractional part of any multiple as random numbers. The disadvantage of the method is that irrational numbers can only be represented as approximate values within the computational accuracy. ${\ displaystyle {\ sqrt {2}}}$ ${\ displaystyle e}$
Recursive arithmetic random number generator : These methods are based on the calculation of a new random number from one or more previous numbers. The newly generated number is saved and is included in the calculation when the random number generator is called up again. At the very first call of the random number generator has an arbitrarily chosen start value, the seed (usually English. Seed ) are used.
- Congruence generator
  - linear congruence generator
    - multiplicative congruence generator
    - mixed linear congruence generator
  - Fibonacci generator
- Inverse congruence generator
- Mersenne twister
- Multiply-with-carry
- Well Equidistributed Long-Period Linear
- Xorshift
- Block or stream ciphers , cryptological hash functions

Hardware-technical implementations

Shift register with feedback
- linear shift register
- non-linear shift register

Hybrid generators

In practice, arithmetic random number generators , which are a hybrid form, are often used . They calculate pseudo-random numbers , but use - if necessary - a genuinely random starting value . However, the entropy of the generated random number cannot be greater than that of the seed value.

In practice, such hybrid random number generators can be found under Unixoid operating systems such as Linux or BSD under /dev/randomand /dev/urandom. These show practically no statistical abnormalities . In most cases, however, they are not initialized using the methods described, but by evaluating the time interval between hardware events (keyboard entries, network traffic and the like), which can also be considered to be random.

In the simplest case, a pseudo-random number generator is selected, which is occasionally restarted with a new real random number as the starting value.

Web links

Wiktionary: Random number generator - explanations of meanings, word origins, synonyms, translations

Real online random number generator (RANDOM.ORG offers true random numbers on the internet)

Individual evidence

↑ timer entropy daemon
↑ D. Meschede (Ed.): Gerthsen Physik . 23rd, revised edition, Springer 2006, p. 986
^ W. Baier (Ed.): Electronics Lexicon . 2nd Edition. Franckh'sche Verlagshandlung, Stuttgart 1982, p. 485.
↑ DJ Kinniment et al .: Design of an on-chip random number generator using metastability . In: Proceedings of the 28th European Solid-State Circuits Conference , 24. – 26. September 2002, pp. 595-598.
↑ Wolfgang Scheibe, Random Giver in Gaming Machines, Automaten-Markt, Issue 5, 1966, pp. 523-534, online ( Memento from August 27, 2019 in the Internet Archive ).
^ DE Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms . Addison-Wesley, Reading (MA) 1997, ISBN 0-201-89684-2 .

[1] timer entropy daemon

[2] D. Meschede (Ed.): Gerthsen Physik . 23rd, revised edition, Springer 2006, p. 986

[3] W. Baier (Ed.): Electronics Lexicon . 2nd Edition. Franckh'sche Verlagshandlung, Stuttgart 1982, p. 485.

[4] DJ Kinniment et al .: Design of an on-chip random number generator using metastability . In: Proceedings of the 28th European Solid-State Circuits Conference , 24. – 26. September 2002, pp. 595-598.

[5] Wolfgang Scheibe, Random Giver in Gaming Machines, Automaten-Markt, Issue 5, 1966, pp. 523-534, online ( Memento from August 27, 2019 in the Internet Archive ).

[6] DE Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms . Addison-Wesley, Reading (MA) 1997, ISBN 0-201-89684-2 .