Pseudorandom number generation
Tags: algorithms
Published: 2022-06-27 09:08:36

<p><span style="font-weight: 400;">Quite often programmers in their work meet with the need of working with random numbers. Most often random numbers are required in modeling, numerical analysis, and testing tasks, but there are many other very specific tasks like:</span></p>
<ul>
<li style="font-weight: 400;"><span style="font-weight: 400;">Random selection of the responder. In this case, one wheel is enough.&nbsp;</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Form mini-groups to work in class or to work on a long-term project.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Choice of tasks for students, both textual and using images.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Formation of sentences. You can represent wheels with sentence members. Students must form sentences with correct word order, cases, etc.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Winged phrases. You can break such phrases, and aphorisms into parts. Start wheels. The students have to indicate the correct or incorrect order of these phrases.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Randomly choose questions from the didactic game.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">And much more..</span></li>
</ul>
<p><span style="font-weight: 400;">They are all easily solved at </span><a href="https://spinnerwheel.com"><span style="font-weight: 400;">SpinnerWheel</span></a><span style="font-weight: 400;">, a relatively new site that provides an easy way to create custom wheel generators to randomly select names, numbers, words, and even images. A feature of SpinnerWheel is the ability to further customize the names, words, numbers, and images that appear in the wheel. You can also customize the sound and visual effects of the spinners you create.</span></p>
<p>&nbsp;</p>
<p><span style="font-weight: 400;">Of course, all modern programming languages have a random function or their analogs. These functions most often give really good pseudorandom numbers, but I've always wondered how these functions work.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">In this topic, I will try to explain how the linear congruential method (which is most often used in the random function) works, and the method of getting random numbers using a polynomial counter (which is often used for hardware testing).</span><span style="font-weight: 400;"><br /><br /></span></p>
<h4><strong>Introduction</strong></h4>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">It is worth saying right away that it makes sense to generate random numbers only with uniform distribution since all other distributions can be obtained from the uniform one using transformations known from probability theory.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">For those who have forgotten or have not yet studied probability theory, let me remind you that in a uniformly distributed sequence of zeros and ones, zeros will occur on average (!) in 50% of cases.&nbsp;</span></p>
<p><span style="font-weight: 400;">However, it does not mean that there will be exactly 500 zeros in a sequence of 1000 digits. Moreover, a sequence of 1000 digits can have 999 zeros, and the probability that the thousandth element will be equal to zero remains equal to 0.5. This seems paradoxical at first sight, but it is important to understand that all sequences are equally probable. If we consider a sufficiently large set of such sequences, then on average(!) each of them will contain 500 zeros.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Having remembered the theory a little bit, we move on to history. In pre-computer times, random numbers were obtained by pulling colorful balls out of bags, drawing cards, and rolling dice. You couldn't do serious research that way, so in 1927 Tippett published the first table of random numbers. A little later, people tried to automate the process somehow. Machines generating random numbers began to appear. Now such devices are also used and are called sources (generators) of entropy. It should be noted that only such devices can give truly random numbers. But, unfortunately, entropy generators are quite expensive, and it is not possible to install them on every PC. This is why the need for algorithms to produce random numbers arose.</span><span style="font-weight: 400;"><br /><br /></span></p>
<h4><strong>The first attempt to obtain an NSP</strong></h4>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Some people think that getting random numbers is easy. In their opinion, it is enough to perform random complex mathematical operations on the original number. If we open the second volume of the famous Knuth, we find that in 1959 Knuth also tried to build a generator based on such an idea. His algorithm looked like this:</span></p>
<ul>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Select the number of iterations.] Assign Y to the largest significant digit of X. (We will perform steps K2-K13 exactly Y+1 times, i.e., apply randomized transformations a random number of times.)</span><span style="font-weight: 400;"><br /><br /></span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Select random step] Assign the next highest significant digit X. Move to step K(3 + Z), i.e. to a randomly chosen step in the program.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Provide &gt; 5 x 109] If X &lt; 5000000000, assign X the value X + 5000000000.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Middle of the square.] Replace X with the middle of the square X</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Multiply.] Replace X with the number (1001001001 X) mod 1010.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Pseudo-complete.] If X &lt; 100000000, assign X the value X + 9814055677; otherwise assign X the value 1010- X.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Rearrange the halves.] Swap the five lowest characters with the highest.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Multiply.] Perform step K5.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Decrease digits.] Decrease each non-zero digit of the decimal representation of the number X by one.</span><span style="font-weight: 400;"><br /><br /></span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">К10. [Modified by 99999.] If A' &lt; 105, assign X the value - X 2 +99999; otherwise assign X the value X - 99999.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Normalize.] (At this step A' cannot be zero.) If X &lt;109, multiply X by 10.</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Modification of the method of mean squares.] Replace X with the mean 10 digits of the number X(X - 1).</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">[Repeat?] If Y &gt; 0, decrease Y by 1 and return to step K2. If Y = 0, the algorithm is complete. The value of number X from the previous step will be the desired "random" value.</span></li>
</ul>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Despite its apparent complexity, this algorithm quickly converged to the number 6065038420, which after a small number of steps converted to itself. The moral of the story is that you can't use a random algorithm to get random numbers.</span><span style="font-weight: 400;"><br /><br /></span></p>
<h4><strong>Linear congruential method</strong></h4>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">In most programming languages, this is the method used in the standard random number function. This method was first proposed by Lehmer in 1949. Four numbers are selected:</span><span style="font-weight: 400;"><br /><br /></span></p>
<ol>
<li style="font-weight: 400;"><span style="font-weight: 400;">Module m (m&gt;0);</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Multiplier a (0&lt;=a&lt;m);</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Increment c (0&lt;=c&lt;m);</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">Initial value X</span><span style="font-weight: 400;">0</span><span style="font-weight: 400;"> (0&lt;= X</span><span style="font-weight: 400;">0</span><span style="font-weight: 400;"> &lt; m)</span></li>
</ol>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">The sequence is obtained using the following recurrence formula: X</span><span style="font-weight: 400;">n+1</span><span style="font-weight: 400;"> =(a* X</span><span style="font-weight: 400;">n</span><span style="font-weight: 400;"> +c) mod m.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">This method gives really good pseudorandom numbers, but if we take the numbers m,a,c arbitrarily, we are likely to be disappointed. With m=7, X</span><span style="font-weight: 400;">0</span><span style="font-weight: 400;"> =1, a=2, c=4 we get the following sequence: 1,6,2,1,6,2,1,...</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">This sequence does not exactly fit the definition of a random sequence. Nevertheless, this failure allowed us to draw two important conclusions:</span><span style="font-weight: 400;"><br /><br /></span></p>
<ol>
<li style="font-weight: 400;"><span style="font-weight: 400;">The numbers m,a,c, X</span><span style="font-weight: 400;">0</span><span style="font-weight: 400;"> must not be random;</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">The linear congruential method gives us repetitive sequences.</span></li>
</ol>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Any function mapping a finite set X to X will give cyclically repeated values. So, our goal is to lengthen as much as possible the unique part of the sequence (by the way, the length of the unique part cannot be more than m).</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Without going into details of the proofs, let us say that the period of the sequence will be equal to m only if the following three conditions are met:</span><span style="font-weight: 400;"><br /><br /></span></p>
<ol>
<li style="font-weight: 400;"><span style="font-weight: 400;">The numbers c and m are mutually prime;</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">a-1 is a multiple of p for every prime p that is a divisor of m;</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">If m is a multiple of 4, then a-1 must also be a multiple of 4.</span></li>
</ol>
<p><span style="font-weight: 400;">At the end of the story about the linear congruential method, we should say that the sequences obtained with its help, although they are sufficiently random, are not cryptographically stable. Because knowing 4 consecutive numbers, the cryptanalyst can make a system of equations, from which we can find a,c,m.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;"><br /><br /></span></p>
<h4><strong>Obtaining pseudorandom numbers based on the polynomial counter (shift register)</strong></h4>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">The algorithm we are going to consider is based on the exclusive OR (sum modulo two) operation. Just in case, let me remind you what the truth table for this function looks like:
<img src="https://i.ibb.co/rc2n2NZ/unnamed-29.png" alt="unnamed-29" border="0">
</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">The circuits shown in the figure below are the simplest polynomial counters. The zero bit in such circuits is calculated based on the exclusive OR function, and all other bits are obtained by a simple shift. The bits from which the signal goes to the exclusive OR are called taps.
<img src="https://lh3.googleusercontent.com/keep-bbsk/AGk0z-PABWsBhxJIwhrjTZO7D8NwAwe6GGxNcwA5v7cxssVSvIUHWJnkrwPYeagwiQg0MgEL64NnHaVwK7HhuFI_AYDyLMLrmWtR7bWpOZlx_MVNElw=s653">
</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Let's look at how the values in these registers will change when the initial value is 001:
<img src="https://keep.google.com/u/0/media/v2/1xuLC-If3sace…2Cimage%2Fpng%2Cimage%2Fwebp%2Caudio%2Faac&sz=171">
</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">Both registers start with the same value, but then the values generated by the registers start to diverge quickly. But after 6 steps, both registers return to their initial state.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">It is easy to show that both of these registers have generated the longest possible sequence, which contains all combinations except zero. That is, if the register bit is m, you can get a sequence of length 2</span><span style="font-weight: 400;">m</span><span style="font-weight: 400;"> -1.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">The polynomial counter of any dimension has many combinations of taps that will provide the sequence of maximum length, using wrong combinations will lead to the generation of short sequences. A separate and quite difficult task is to find these combinations of taps.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">It is worth noting that these combinations are not always unique. For example, for a 10-bit counter, there are two: [6;9] and [2;9], for a six-bit counter there are twenty-eight such combinations.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">To find these combinations, we need to represent the counter as a polynomial. The counters from the example will have the following form: x</span><span style="font-weight: 400;">2</span><span style="font-weight: 400;"> XOR 1 and x</span><span style="font-weight: 400;">2</span><span style="font-weight: 400;"> XOR x XOR 1.</span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">From theory, we know that a necessary and sufficient condition for generating a complete sequence is the primitiveness of the characteristic polynomial. This means that:</span><span style="font-weight: 400;"><br /><br /></span></p>
<ul>
<li style="font-weight: 400;"><span style="font-weight: 400;">A characteristic polynomial cannot be represented as a product of polynomials of a lower degree;</span></li>
<li style="font-weight: 400;"><span style="font-weight: 400;">The characteristic polynomial is a divisor of the polynomial z</span><span style="font-weight: 400;">&delta;</span><span style="font-weight: 400;"> XOR 1, at(&delta;=2</span><span style="font-weight: 400;">m</span><span style="font-weight: 400;"> -1, and is not a divisor at any other values of &delta;&lt;2</span><span style="font-weight: 400;">m</span><span style="font-weight: 400;"> -1.</span></li>
</ul>
<p><span style="font-weight: 400;"><br /></span><span style="font-weight: 400;">The advantages of the polynomial counter are simplicity, both software and hardware implementation, speed of operation, and cryptographic stability.</span></p>