Congruence generator

The congruence generators are a class of algorithms that generate random looking sequences of numbers . The numbers generated thereby is called pseudo random numbers because they deterministically generated and thus not really happen to have. Congruence generators are the best known and most widely used recursive arithmetic random number generators .

General congruence generator

A congruence generator is defined by the following parameters:

• Number of status values ${\displaystyle n\in \mathbb {N} ^{+}}$
• module ${\displaystyle m\in \{2,3,4,\ldots \}}$
• Factors with ${\displaystyle a_{1},\ldots ,a_{n}\in \left\{0,\ldots ,m-1\right\}}$ ${\displaystyle a_{n}>0}$
• Increment ${\displaystyle b\in \left\{0,\ldots ,m-1\right\}}$
• Start values (not all 0, if ) ${\displaystyle y_{1},\ldots ,y_{n}\in \left\{0,\ldots ,m-1\right\}}$ ${\displaystyle b=0}$

For now you bet ${\displaystyle i>n}$

${\displaystyle y_{i}=\left(\left(\sum _{k=1}^{n}a_{k}y_{i-k}\right)+b\right)\,{\bmod {\,}}m}$. Denotes the remainder of the division; see modulo . ${\displaystyle \mod {}}$

The calculated numbers are used as random numbers. ${\displaystyle y_{i}}$

The state of the generator before the generation of is given by the values . This state defines (given ) all subsequent random numbers, since the next random number and the next state are determined by the current state. There are possible states, and therefore an earlier state must be repeated at the latest after taking steps. The congruence generator thus generates a periodic sequence of numbers, the period length can also be significantly smaller than . In the extreme case it is 1, and the generator always generates the same “random number”. When defining the parameters, it is therefore important, among other things, to ensure a sufficient period length. ${\displaystyle y_{i}}$ ${\displaystyle y_{i-n},\ldots ,y_{i-1}}$ ${\displaystyle n,m,a_{k},b}$ ${\displaystyle m^{n}}$ ${\displaystyle m^{n}}$ ${\displaystyle m^{n}}$

If you need real random numbers in the interval , you can use the approximation ${\displaystyle [0,1)}$

${\displaystyle u_{i}:={\frac {y_{i}}{m}}}$

use if the modulo is large enough to give a sufficiently fine subdivision. ${\displaystyle m}$

Linear congruence generator

With you get the special case of a linear congruence generator . At it is called a multiplicative congruence generator , and for others it is called a mixed linear congruence generator . ${\displaystyle n=1}$ ${\displaystyle b=0}$ ${\displaystyle b}$

The latter is used more often and has four natural numbers as parameters:

• module ${\displaystyle m\in \{2,3,4,\ldots \}}$
• factor ${\displaystyle a\in \{1,\ldots ,m-1\}}$
• Increment ${\displaystyle b\in \{1,\ldots ,m-1\}}$
• Starting value ${\displaystyle y_{1}\in \{0,\ldots ,m-1\}}$

The further values ​​are then calculated from the start value using the following formula : ${\displaystyle i\geq 2}$

${\displaystyle y_{i}=(ay_{i-1}+b)\ {\bmod {\ }}m}$

The linear congruence generator was introduced by Derrick Henry Lehmer in 1949 . It is used in the runtime libraries of various programming languages to generate pseudo random numbers, e.g. B. in C / C ++ (function rand () in the header file stdlib.h).

In cryptography , however, the linear congruence is not used because it has the parameters of a few values of the number sequence and can calculate and thus the complete sequence of numbers. ${\displaystyle a}$ ${\displaystyle b}$

Period length

According to Knuth's theorem, linear congruence generators reach their maximum possible period length if the following requirements are met: ${\displaystyle m}$

• The increment is relatively prime to the module . ${\displaystyle b}$ ${\displaystyle m}$
• Every prime factor of divides . ${\displaystyle m}$ ${\displaystyle a-1}$
• If is divisible by 4, then too . ${\displaystyle m}$ ${\displaystyle a-1}$

In this case the generator will generate every number from 0 to exactly once and then start over. So it delivers a pseudo-random permutation of these numbers. The starting value can then be any number from this set. ${\displaystyle m-1}$ ${\displaystyle y_{1}}$

The multiplicative congruence generator (mit ) must therefore have a period length smaller than . The set of Carmichael says, with given its period length is exactly maximized if: ${\displaystyle b=0}$ ${\displaystyle m}$ ${\displaystyle m}$

• ${\displaystyle y_{1}}$is too coprime ${\displaystyle m}$
• ${\displaystyle a}$is a primitive element modulo . ${\displaystyle m}$

For some special cases of , the primitive elements can easily be determined modulo : ${\displaystyle m}$ ${\displaystyle m}$

• If it is a power of two , then mod 8 must yield the remainder 3 or 5. The period length is then , and the start value must be odd. There are two periods, each half of the odd numbers from to . ${\displaystyle m}$ ${\displaystyle \geq 16}$ ${\displaystyle a}$ ${\displaystyle m/4}$ ${\displaystyle y_{1}}$ ${\displaystyle 1}$ ${\displaystyle m-1}$
• When a prime number , then must for all prime factors of apply: . Then the period length is . The start value must not be zero. ${\displaystyle m}$ ${\displaystyle \geq 3}$ ${\displaystyle q}$ ${\displaystyle m-1}$
  ${\displaystyle a^{(m-1)/q}\ {\bmod {\ }}m\neq 1}$ ${\displaystyle m-1}$ ${\displaystyle y_{1}}$

Defects in the numbers generated

The linear congruence generator does not provide numbers that appear completely random. It can be shown that there is a dependency on consecutive numbers.

Partial period

Often one chooses , whereby the word length of the computer is in bits , because then one does not have to calculate the modulo division explicitly. It arises automatically by cutting off the overflow bits. In this case the least significant bits of the status number behave like a generator with the module . These bits repeat themselves at the latest after steps. This means, in particular, that the least significant bit has period 2 at best, that is, changes regularly between 0 and 1. With the multiplicative congruence generator it is even constant. ${\displaystyle m=2^{e}}$ ${\displaystyle e}$ ${\displaystyle x}$ ${\displaystyle y_{i}}$ ${\displaystyle 2^{x}}$ ${\displaystyle 2^{x}}$

In general, the following applies to all linear congruence generators: if is a divisor of the module , then a sequence of numbers with the period results : ${\displaystyle d}$ ${\displaystyle m}$ ${\displaystyle y_{i}\ {\bmod {\ }}d}$ ${\displaystyle o\leq d}$

a valid: . ${\displaystyle o\in \{1,\ldots ,d\}}$ ${\displaystyle \forall i:y_{i+o}\equiv y_{i}\ ({\bmod {\ }}d)}$

If the generator has the period according to Knuth's theorem , then the length of the partial period is exactly for all divisors of . ${\displaystyle m}$ ${\displaystyle o}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle m}$

Because of this subperiod behavior, it is unfavorable to obtain random numbers through if and are not relatively prime . Then, the remainder would be a number that and divides a period of a maximum length run through. If you z. B. wants to simulate a six-sided dice and is even, then returns numbers that are alternately even and odd. ${\displaystyle r_{i}\in \{0,\ldots ,k-1\}}$ ${\displaystyle r_{i}:=y_{i}\ {\bmod {\ }}k}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle r_{i}\ {\bmod {\ }}d}$ ${\displaystyle d}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle d}$ ${\displaystyle m}$ ${\displaystyle r_{i}:=y_{i}\ {\bmod {\ }}6}$

Possible remedy:

• A mixed linear congruence generator with a period is used , whereby the module is chosen to be coprime. The results are not evenly distributed, but the deviation from the uniform distribution is only small and can often be neglected. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle k}$ ${\displaystyle r_{i}:=y_{i}\ {\bmod {\ }}k}$ ${\displaystyle k\ll m}$
• One uses a multiplicative congruence generator with period and chooses for a large prime number. Also, if is a multiple of , they are also evenly distributed. ${\displaystyle m-1}$ ${\displaystyle m}$ ${\displaystyle m-1}$ ${\displaystyle k}$ ${\displaystyle r_{i}}$
• A rejection method is set and used with the most significant bits of . The will to bit to the right pushed , with the smallest power of two is . Only those are used , the rest are discarded. This method delivers evenly distributed results. ${\displaystyle m=2^{e}}$ ${\displaystyle y_{i}}$ ${\displaystyle y_{i}}$ ${\displaystyle e-f}$ ${\displaystyle 2^{f}}$ ${\displaystyle \geq k}$ ${\displaystyle r_{i}:=\lfloor y_{i}/2^{e-f}\rfloor }$ ${\displaystyle r_{i}<k}$
• One calculates where the smallest is prime to coprime and is discarded. ${\displaystyle r_{i}:=y_{i}\ {\bmod {\ }}x}$ ${\displaystyle x}$ ${\displaystyle m}$ ${\displaystyle \geq k}$ ${\displaystyle r_{i}\geq k}$
• Some implementations of a linear congruence generator circumvent the problem in that they only supply the more significant part of the state value as a result. E.g. is and the result delivered to the user is with . ${\displaystyle y_{i}}$ ${\displaystyle m=2^{e}}$ ${\displaystyle \lfloor y_{i}/2^{b}\rfloor }$ ${\displaystyle 2b=e}$

Hyperplane Behavior

“Hyperplane behavior” of a linear congruence generator in three dimensions

Mixed congruential: . This generator is used in the TI-59 from Texas Instruments . Overlapping triples are shown, i.e. h., , , etc. Without overlaps only every third level would be left. ${\displaystyle x_{n+1}=24298x_{n}+99991\ {\bmod {\ }}199017}$ ${\displaystyle (x_{1},x_{2},x_{3})}$ ${\displaystyle (x_{2},x_{3},x_{4})}$ ${\displaystyle (x_{3},x_{4},x_{5})}$

The linear congruence generator exhibits a hyperplane behavior, see Marsaglia's theorem . By suitable choice of the parameters , and , one can optimize the behavior of the generator and achieve a large number of hyperplanes. Given the following rules of thumb , one can build : ${\displaystyle m}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle m}$ ${\displaystyle a}$

• ${\displaystyle a}$ shouldn't be too big or too small, like: ${\displaystyle 0{,}01\cdot m<a<0{,}99\cdot m}$
• ${\displaystyle a}$should be chosen as randomly as possible, ie not be a "round" number in dual or decimal representation.
• With the mixed linear congruence generator, the potency should be as large as possible. It is the minimum value for which is a multiple of . Donald Knuth recommends that the potency should be at least 5. If so , then it should be to get the maximum possible potency . ${\displaystyle s}$ ${\displaystyle (a-1)^{s}}$ ${\displaystyle m}$ ${\displaystyle m=2^{e}}$ ${\displaystyle a\ {\bmod {\ }}8=5}$ ${\displaystyle \lceil e/2\rceil }$

If you want to be sure that the generator generates good random numbers, you should not rely on these rules of thumb alone, but rather test the generator with the spectral test.

Because of the hyperplane behavior, the inverse congruence generator , which does not have this problem, is occasionally used instead of the linear congruence generator . However, it requires a higher computational effort. It is not a special case of the general congruence generator.

Fibonacci generator

A Fibonacci generator is also a congruence generator (with , and ) and consists of the following components: ${\displaystyle n=2}$ ${\displaystyle b=0}$ ${\displaystyle a_{1}=a_{2}=1}$

• module ${\displaystyle m\in \{2,3,4,\dotsc \}}$
• Starting values ${\displaystyle y_{1},y_{2}\in \{0,\dotsc ,m-1\}}$

It should be. ${\displaystyle \operatorname {ggT} (m,y_{1},y_{2})=1}$

The pseudo random numbers are generated with the following formation rule:

${\displaystyle y_{i}=(y_{i-1}+y_{i-2}){\bmod {m}}\quad ({\text{mit }}i\geq 3)}$

One characteristic is that the cases or never occur. Fibonacci generators are therefore not very suitable as pseudo random number generators. This is especially true for mathematical objects that require more than two random numbers to generate. For example, if you were to try to generate a random point cloud in a cube, all points would be on two levels. ${\displaystyle y_{i-1}<y_{i+1}<y_{i}}$ ${\displaystyle y_{i}<y_{i+1}<y_{i-1}}$

Delayed Fibonacci generator

The principle of the Fibonacci generator can, however, be generalized by not using the last two state values , but rather further back state values ​​to generate the new random number. This results in a lagged Fibonacci generator : ${\displaystyle y_{i}}$

${\displaystyle y_{i}=(y_{i-B}+y_{i-A}){\bmod {m}}\quad {\text{mit }}A,B\in \mathbb {N} ^{+},\ A>B;\quad i>A}$

with the starting values ${\displaystyle y_{1},\dotsc ,y_{A}\in \{0,\dotsc ,m-1\}}$

So then is and , the rest are zero. As a rule, one chooses even and and so that the polynomial in ${\displaystyle n=A}$ ${\displaystyle a_{A}=a_{B}=1}$ ${\displaystyle a_{k}}$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle x}$

${\displaystyle x^{A}+x^{B}+1}$

is a primitive polynomial modulo 2 . Then the period length of the generator is at least . ${\displaystyle 2^{A}-1}$

The following table shows some value pairs for and that meet this condition: ${\displaystyle A}$ ${\displaystyle B}$

A.	2	31	55	73	98	100	135	258	607	3217	23209
B.	1	13	24	25th	27	37	22nd	83	273	576	9739

${\displaystyle x^{A}+x^{B}+1}$is a primitive polynomial modulo 2 if and only if this is true for. So you can use instead of always . ${\displaystyle x^{A}+x^{A-B}+1}$ ${\displaystyle B}$ ${\displaystyle A-B}$

This generator is also used in practice. However, it also does not provide any numbers that appear completely random. The problem with the simple Fibonacci generator is only shifted: You never have or . There are also other flaws. ${\displaystyle y_{i-A}<y_{i}<y_{i-B}}$ ${\displaystyle y_{i-B}<y_{i}<y_{i-A}}$

As a remedy, it was suggested to only use consecutive numbers and then discard the next to numbers. This works fine, but at the cost of 5 to 11 times the computational effort. The ranarray generator proposed by Donald Knuth works in this way. He has and , and of 1009 consecutive numbers only ever a block of 100 numbers is used. ${\displaystyle A}$ ${\displaystyle 4A}$ ${\displaystyle 10A}$ ${\displaystyle A=100}$ ${\displaystyle B=37}$

To ensure the period , it only depends on the least significant bit in the status values , i.e. on whether they are even or odd. The more significant bits can be modified as desired in order to improve the quality of the random numbers obtained. For example: ${\displaystyle 2^{A}-1}$ ${\displaystyle y_{i}}$

${\displaystyle y_{i}=(y_{i-A}+y_{i-B}+f(y_{i-C})){\bmod {m}};\quad f\colon \{0,\dotsc ,m-1\}\to \{0,2,4,6,\dotsc \},\;C\in \{1,\dotsc ,n\}}$

Other

The delayed Fibonacci generator can be generalized further by processing more than two state values:

${\displaystyle y_{i}=\left(\sum _{k\in M}y_{i-k}\right){\bmod {m}}\quad {\text{mit}}\quad M\subset \mathbb {N} ^{+}}$.

${\displaystyle n}$is the biggest element in here . In order to guarantee a period of at least , the corresponding polynomial must also be used here ${\displaystyle M}$ ${\displaystyle 2^{n}-1}$

${\displaystyle \sum _{k\in M}x^{k}+1}$ or the equivalent of the polynomial ${\displaystyle x^{n}+\sum _{k\in M}x^{n-k}}$

be a primitive polynomial modulo 2 (with an even module ). A generator constructed in this way with generally delivers better random numbers than with , but again at the price of a higher computational effort. ${\displaystyle m}$ ${\displaystyle |M|>2}$ ${\displaystyle |M|=2}$

With a further generalization one can increase the period length given a given and probably also further improve the quality of the random numbers. be a prime factor of . for the calculation rule ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle m}$

${\displaystyle y_{i}=\left(\sum _{k=1}^{n}a_{k}y_{i-k}\right){\bmod {m}}}$

are chosen in such a way that the polynomial in ${\displaystyle a_{k}\in \{0,\dotsc ,m-1\}}$ ${\displaystyle a_{n}\not \equiv 0{\pmod {p}}}$ ${\displaystyle x}$

${\displaystyle x^{n}-\sum _{k=1}^{n}(a_{k}{\bmod {p}})x^{n-k}}$

is a primitive polynomial modulo ${\displaystyle p}$ . Then the period length is at least . The previous generator results from this with and as a special case, and delivers a multiplicative congruence generator with the period length . ${\displaystyle p^{n}-1}$
${\displaystyle p=2}$ ${\displaystyle a_{k}\in \{0,1\}}$ ${\displaystyle n=1;\ p=m}$ ${\displaystyle p-1}$

The polynomial is a primitive polynomial modulo if the following conditions are met: ${\displaystyle f(x)=x^{n}-\sum _{k=1}^{n}a_{k}x^{n-k}}$ ${\displaystyle p}$

( ) ${\displaystyle {\text{sei }}r={\frac {p^{n}-1}{p-1}}{\text{ und }}a=(-1)^{n-1}a_{n}}$

• ${\displaystyle a}$ is a primitive element modulo ${\displaystyle p}$
• the polynomial is congruent to (modulo ) ${\displaystyle x^{r}}$ ${\displaystyle a}$ ${\displaystyle f(x)}$
• for all prime factors of the degree of the polynomial is positive ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle x^{r/q}{\bmod {f}}(x)}$

Polynomial arithmetic is used (see polynomials and polynomial division ), and the coefficients are calculated modulo (they are elements of the remainder class ring ). ${\displaystyle p}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

See also

• List of random number generators

Individual evidence

1. ^ Donald E. Knuth : The Art of Computer Programming . Volume 2: Seminumerical Algorithms. 3. Edition. Addison-Wesley, 1997, ISBN 0-201-89684-2 , pp. 10-26
2. ↑ StackOverflow forum: Understanding the algorithm of Visual C ++ 's rand () function

Web links

Treatise on bitstream encryptions