Pseudo-random

This article is not adequately provided with supporting documents (for example individual proofs ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

As a pseudo-random is called what happened to appear, but in fact predictable is. In this sense, pseudo-random number generators , such as cryptographically secure random number generators , generate pseudo -random numbers.

Pseudo randomness in computability theory

In the theory of predictability , everything is referred to as pseudo-random that, from the perspective of the observer, cannot be distinguished from real randomness. For example, the result of a coin toss is generally considered to be random. If the coin is already in the air, it is theoretically possible to predict the outcome based on its rotation, speed, etc. However, the litter still appears randomly to someone who does not have the appropriate measuring devices (and computing capacity); the toss of the coin in the air is pseudo-random for him . In general, predictability theory defines as pseudo-random what can not be predicted by efficient algorithms . However, pseudo-randomness is still computable (it can be generated efficiently), just not predictable. Pseudo-random generators according to this definition of pseudo-randomness assume the existence of explicit hard functions .

Pseudo random numbers

The most important application of pseudo-random numbers are the so-called random number generators , which are available in practically all programming languages . The fact that these are mostly just pseudo random number generators (English PRNG, pseudo random number generator) is often overlooked. They generate a sequence of numbers that looks random , but is not because it is calculated by a deterministic algorithm . Each time the random number calculation is started with the same starting value, the so-called seed , the same pseudo-random number sequence is generated.

They violate certain properties of real random numbers , but are much easier to produce by computers . Periodic sequences of numbers are often generated, i.e. the same numbers are repeated after a certain length. The advantage of PRNGs is their high speed. The period can be made sufficiently large by a clever choice of parameters. Some pseudorandom number generators only generate finite sequences of numbers.

Use of pseudo random numbers

Find pseudo random numbers u. a. application

• in computer simulation , in which stochastic processes are simulated with the help of software ( Monte Carlo simulation )

• when troubleshooting computer programs

• in the artificial generation of noise

• in the spread spectrum technique

• in the field of cryptography

It is inappropriate to use pseudo-random numbers in areas where real randomness is required. To generate true random numbers , one needs either a real random number generator (e.g. by digitizing noise or by taking advantage of quantum effects ) or at least a source of quasi-random (normally unpredictable) events such as times of user input or network activity.

Non-periodic / infinite generator

Take the decimal places of a root of an integer as random numbers. Of course, it is important to ensure that the resulting root is an irrational number , that is, whatever is the case if the root is not an integer. Classically, you can use the circle number Pi instead of. Due to the finite storage capacity of a computer, however, there can be no non-periodic deterministic random number generator in practice. However, non-periodic deterministic random number generators with two clock generators whose clocks are incommensurable are possible; if their frequency ratio is an irrational number, i.e. is not fulfilled. Among the real numbers because the rational numbers a Lebesgue - null set form, it is virtually always the case and thus a generated from two bars signal not periodic. An example of this is a pseudo-random signal generated with the frequency , which is scanned / read in with the frequency . ${\displaystyle {\sqrt {n}}\notin \mathbb {Q} }$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\tfrac {f_{1}}{f_{2}}}}$ ${\displaystyle n_{1}\cdot f_{1}=n_{2}\cdot f_{2}}$ ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$

Generation of pseudo-random numbers using primitive polynomials

Primitive polynomials define a recurring relation that can be used to generate bits of pseudorandom numbers. In fact, each linear feedback shift register with maximum cycle (this is 2 ^{lrsr length} - 1) is related to primitive polynomials.

Be z. B. given a primitive polynomial . One begins (English with a custom seed seed , seed , this need not necessarily be chosen randomly). You then take the 10th, 3rd and 0th bit , counted from the least significant bit, combine them with XOR and get a new bit. The seed number is then shifted to the left and the new bit becomes the least significant bit of the seed number. This can be repeated to generate pseudo-random bits. Very specific outputs of the shift register are required for a maximum length sequence . ${\displaystyle X^{10}+X^{3}+1}$ ${\displaystyle 2^{10}-1=1023}$

In general, for a primitive polynomial of degree , this process generates pseudo-random numbers before the sequence repeats. ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$

literature

• Donald E. Knuth: The Art of Computer Programming. Pearson Education, 3rd Edition 1997.
• Harvard.edu: pseudorandomness

Web links

• The website naRND is a documentation about non-arithmetic (pseudo-) random numbers

Individual evidence

1. ↑ Tietze / Schenk, "Semiconductor Circuit Technology", 3rd edition 1976, p. 590 ff, no longer described in later editions.