Methods of generating random numbers with a uniform distribution law. Part 1
Introduction
Industry does not stand still. Back in 1990, pseudo-random numbers, as long as 40 bits, generated on a computer could be guessed in a few hours [1]. Today, the qualitative characteristics of pseudo-random variables on a computer affect even experienced mathematicians. In many areas of application of generation algorithms for all-random numbers, there are a number of limitations associated with this or that lack of methods for generating them. Improving existing methods contributes to the high interest in the topic, which increases with an increase in the number of publications. Let this article be my contribution to the development of methods for modeling and generating random processes, so important for my research and development.
Prehistory
A brief insight into the history of random number generation methods shows that in the pursuit of stochasticity, the developers were ready to go to extreme measures. So in 1996, a source of random numbers called Lavarand was invented and launched. The method of generating numbers was reduced to processing a photo of a decorative lamp - a lava lamp, which continuously changed its appearance in an unpredictable way [2]. It is also worth mentioning about the first random variable generators on ordinary computers. Intel developed them in 1999 and called this component Firmware Hub. The generation method was to register thermal noise of resistors, followed by amplification and using an oscillator as a control signal, regularly changing its value between “0” and “1” [3]. Such a system operated continuously, regardless of the user's need to use the random generation system numbers
The main problem of generating truly random numbers is the mandatory presence of the analog component, since the qualitative characteristics of digital methods for generating pseudo-random numbers do not meet many standards of the National Institute of Standards and Technology, and in practice they are absolutely not suitable for solving many applied problems, such as cryptography.
')
Fig.1 Diagram of a random number generator.
In April 2012, the first microarchitecture processors codenamed “Ivy Bridge” went on sale. A feature of this architecture was the presence of a generator that allows the use of analog thermal noise directly to generate random numbers [4]. Figure 1 presents the scheme of such a generator. At first glance, it is too idealized, since the equal appearance of a “0” or “1” can be achieved only with the absolute identity of the inverters, which is impossible in practice. Therefore, the non-uniformity of the generated numbers must be compensated, which is done in the post-processing.
Generating random numbers with a uniform distribution law
Perhaps the most important and irreplaceable methods for modeling random processes are methods for generating equally probable random variables, since most of the algorithms for modeling random processes with an arbitrary distribution law are based on them [5].
The most popular ways to obtain evenly distributed random variables are:
• Tables of random numbers
• Physical random number generators (such as Firmware Hub or random number generator in “Ivy Bridge”)
• Using digital generators or sensors using formulas.
It should be noted that in the last paragraph the pseudo-random numbers are the result of generation. No matter how paradoxical the following statement sounds, the main drawback of such numbers is that in most cases they are not difficult to predict, and in some generation algorithms their sequence also tends to repeat from time to time. In some applications, this is unacceptable, but despite this, it is these methods of generating random variables with a uniform distribution law that are most widely used, due to the simplicity of their implementation on the digital computers.
Among them, the most popular are:
• Congruent methods.
• Methods based on the use of a linear feedback shift register (LFSR).
The linear congruential method is still used to generate random numbers in the most popular programming environments such as MSVS [6], MSVB [7], Java [6], Borland C / C ++ [6], GCC [8], and others. The prevalence of this method indicates its effectiveness.
The essence of the methods of this class is to calculate the sequence of random numbers Y (n):
Y (n + 1) = (x * Y (n) + c)% m,
where m is the number of values ​​from which the sequence is formed (m ≥ 2),% is the remainder of division, x is a multiplier (0 ≤ x <m), c is the increment (0 ≤ c <m), Y (0) is the initial value (0 ≤ Y (0) <m) [9].
The choice of numbers m, x, c, Y (0) depends on the qualitative stochastic parameters of the numbers obtained.
Perhaps the most versatile in use is the class of methods using shift registers. They are indispensable, as in the tasks of cryptography [10] (GSM, Bluetooth) and testing of digital devices [11]. There are references to the use of one of these algorithms as a clock divider or counter [12]. Also algorithms using the shift register are used in scrambling problems [13].
Fig.2 Scheme of the shift register with feedback
The simplest implementation of this algorithm is shown in Fig.2. After setting the initial state of the shift register, every clock out of it reads an all-random bit. Then, over the number, some mathematical operations that depend on a specific implementation occur, the result of which is written after the shift to the “freed” bit of the register.
Conclusion
Of course, far from all are considered, methods for generating random numbers. But they are universally used in various tasks, whether it be simulation of stochastic non-stationary processes for the synthesis of algorithms for determining the angle of a low-flying target or cryptography and scrambling of a code sequence. Since it is possible to calculate the results of the work of such algorithms, without knowing the input data, albeit with the expense of significant resources, the question of their refinement is highly relevant.
List of sources used:
[1] Goldberg, I. Randomness and the Netscape Browser / I. Goldberg, D. Wagner // Dr. Dobb's Journal. - 1996. - January, P.66-70.
[2] US Patent No. 7031991 B2 Hadamard-transform on-line randomness test / Laszlo Hars 17 apr. 2002
[3] Jun, B. The Intel Random Number Generator / B. Jun, P. Kocher // Cryptography Research Inc. white paper, 1999.
[4] How the new Intel random number generator works
[5] Monakov, A. A. Basics of mathematical modeling of radio systems: studies. allowance / A. A. Monakov; GuaP. SPb., 2005. 15 p.
[6] ISO / IEC 9899: 201x Last public Committee Draft from April 12, 2011, page 346f.
[7] How does the Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft support. Microsoft
[8] GNU Scientific Library: Other random number generators
[9] Donald Knut. Volume 2. The computed methods // Programming Art. Decree. cit. - pp. 21—37.
[10] Barklan E., Biham E., Keller N. Instant ciphertext-only cryptanalysis of GSM encrypted communication. - Journal of cryptology â„–21-3, 2008.
[11] Larin, A. L. Basics of digital electronics: study guide / A.L. Larin; M .: MIPT, 2008. - 314 p. - ISBN 978-5-7417-0228-4.
[12] Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators
[13] Vargauzin, V. Principles of digital television standard ATSC / V. Vargauzin - Tele-Satellite Journal No. 9 (47), 1999.
Industry does not stand still. Back in 1990, pseudo-random numbers, as long as 40 bits, generated on a computer could be guessed in a few hours [1]. Today, the qualitative characteristics of pseudo-random variables on a computer affect even experienced mathematicians. In many areas of application of generation algorithms for all-random numbers, there are a number of limitations associated with this or that lack of methods for generating them. Improving existing methods contributes to the high interest in the topic, which increases with an increase in the number of publications. Let this article be my contribution to the development of methods for modeling and generating random processes, so important for my research and development.
Prehistory
A brief insight into the history of random number generation methods shows that in the pursuit of stochasticity, the developers were ready to go to extreme measures. So in 1996, a source of random numbers called Lavarand was invented and launched. The method of generating numbers was reduced to processing a photo of a decorative lamp - a lava lamp, which continuously changed its appearance in an unpredictable way [2]. It is also worth mentioning about the first random variable generators on ordinary computers. Intel developed them in 1999 and called this component Firmware Hub. The generation method was to register thermal noise of resistors, followed by amplification and using an oscillator as a control signal, regularly changing its value between “0” and “1” [3]. Such a system operated continuously, regardless of the user's need to use the random generation system numbers
The main problem of generating truly random numbers is the mandatory presence of the analog component, since the qualitative characteristics of digital methods for generating pseudo-random numbers do not meet many standards of the National Institute of Standards and Technology, and in practice they are absolutely not suitable for solving many applied problems, such as cryptography.
')
Fig.1 Diagram of a random number generator.
In April 2012, the first microarchitecture processors codenamed “Ivy Bridge” went on sale. A feature of this architecture was the presence of a generator that allows the use of analog thermal noise directly to generate random numbers [4]. Figure 1 presents the scheme of such a generator. At first glance, it is too idealized, since the equal appearance of a “0” or “1” can be achieved only with the absolute identity of the inverters, which is impossible in practice. Therefore, the non-uniformity of the generated numbers must be compensated, which is done in the post-processing.
Generating random numbers with a uniform distribution law
Perhaps the most important and irreplaceable methods for modeling random processes are methods for generating equally probable random variables, since most of the algorithms for modeling random processes with an arbitrary distribution law are based on them [5].
The most popular ways to obtain evenly distributed random variables are:
• Tables of random numbers
• Physical random number generators (such as Firmware Hub or random number generator in “Ivy Bridge”)
• Using digital generators or sensors using formulas.
It should be noted that in the last paragraph the pseudo-random numbers are the result of generation. No matter how paradoxical the following statement sounds, the main drawback of such numbers is that in most cases they are not difficult to predict, and in some generation algorithms their sequence also tends to repeat from time to time. In some applications, this is unacceptable, but despite this, it is these methods of generating random variables with a uniform distribution law that are most widely used, due to the simplicity of their implementation on the digital computers.
Among them, the most popular are:
• Congruent methods.
• Methods based on the use of a linear feedback shift register (LFSR).
The linear congruential method is still used to generate random numbers in the most popular programming environments such as MSVS [6], MSVB [7], Java [6], Borland C / C ++ [6], GCC [8], and others. The prevalence of this method indicates its effectiveness.
The essence of the methods of this class is to calculate the sequence of random numbers Y (n):
Y (n + 1) = (x * Y (n) + c)% m,
where m is the number of values ​​from which the sequence is formed (m ≥ 2),% is the remainder of division, x is a multiplier (0 ≤ x <m), c is the increment (0 ≤ c <m), Y (0) is the initial value (0 ≤ Y (0) <m) [9].
The choice of numbers m, x, c, Y (0) depends on the qualitative stochastic parameters of the numbers obtained.
Perhaps the most versatile in use is the class of methods using shift registers. They are indispensable, as in the tasks of cryptography [10] (GSM, Bluetooth) and testing of digital devices [11]. There are references to the use of one of these algorithms as a clock divider or counter [12]. Also algorithms using the shift register are used in scrambling problems [13].
Fig.2 Scheme of the shift register with feedback
The simplest implementation of this algorithm is shown in Fig.2. After setting the initial state of the shift register, every clock out of it reads an all-random bit. Then, over the number, some mathematical operations that depend on a specific implementation occur, the result of which is written after the shift to the “freed” bit of the register.
Conclusion
Of course, far from all are considered, methods for generating random numbers. But they are universally used in various tasks, whether it be simulation of stochastic non-stationary processes for the synthesis of algorithms for determining the angle of a low-flying target or cryptography and scrambling of a code sequence. Since it is possible to calculate the results of the work of such algorithms, without knowing the input data, albeit with the expense of significant resources, the question of their refinement is highly relevant.
List of sources used:
[1] Goldberg, I. Randomness and the Netscape Browser / I. Goldberg, D. Wagner // Dr. Dobb's Journal. - 1996. - January, P.66-70.
[2] US Patent No. 7031991 B2 Hadamard-transform on-line randomness test / Laszlo Hars 17 apr. 2002
[3] Jun, B. The Intel Random Number Generator / B. Jun, P. Kocher // Cryptography Research Inc. white paper, 1999.
[4] How the new Intel random number generator works
[5] Monakov, A. A. Basics of mathematical modeling of radio systems: studies. allowance / A. A. Monakov; GuaP. SPb., 2005. 15 p.
[6] ISO / IEC 9899: 201x Last public Committee Draft from April 12, 2011, page 346f.
[7] How does the Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft support. Microsoft
[8] GNU Scientific Library: Other random number generators
[9] Donald Knut. Volume 2. The computed methods // Programming Art. Decree. cit. - pp. 21—37.
[10] Barklan E., Biham E., Keller N. Instant ciphertext-only cryptanalysis of GSM encrypted communication. - Journal of cryptology â„–21-3, 2008.
[11] Larin, A. L. Basics of digital electronics: study guide / A.L. Larin; M .: MIPT, 2008. - 314 p. - ISBN 978-5-7417-0228-4.
[12] Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators
[13] Vargauzin, V. Principles of digital television standard ATSC / V. Vargauzin - Tele-Satellite Journal No. 9 (47), 1999.
Source: https://habr.com/ru/post/301900/
All Articles