This paper presents the results of the development and research of a pseudorandom number generator based on computing the square root of a prime number. The square root of a prime number is one of the known irrational numbers. According to a well-known hypothesis in mathematics, the sequence of digits of such numbers is a pseudorandom non-periodic digit sequence. Therefore, calculating the square root of a prime number can serve as the basis for constructing a pseudorandom number generator. The key of such a generator can be a simple number and the digit position number from which the regeneration process starts. To efficiently compute the square root in a “bit by bit” style, a modified bisection method is proposed. The proposed method allows saving one multiplication operation in each iteration of the bisection method. At the same time, the complexity of one iteration of the proposed method is close to the complexity of a single addition operation.
In mathematics, there is a well-known hypothesis regarding the normality of irrational and transcendental numbers, in particular, the square roots of prime numbers [10, 11]. This means that the sequence of digits of the square root of a prime number is pseudorandom digit sequence.The mentioned hypothesis has not been proven yet. It remains one of the most famous unsolved problems in mathematics. Interest in calculating the square root of a prime number arose a very long time ago [12]. In particular, among collections of Babylonian historical artifacts preserved at Yale University, there is a round clay tablet (Fig. 1). It is dated to 1750 BC. The tablet shows a square divided by diagonals. Three digits are clearly inscribed on it with cuneiform characters. When the inscription was deciphered, it became clear that almost 4000 years ago in Babylon they already knew how to determine the diagonal of a square based on its side length by multiplying the side by the square root of two. The markings on the tablet provide an approximate value of √2 in 24 51 10 four sexagesimal digits, which corresponds to eight decimal digits 1+ + + =1.41421296 60 602 603
The task of calculating as many digits as possible of the square root of a prime number remains relevant today. One of the notable modern achievements in this area is the work of Professor Jacques Dutka, a staff member of the Department of Mathematical Methods in Engineering at Columbia University. He developed an algorithm and calculated the value of the square root of two up to the one-million eighty-second decimal place. However, the record was soon surpassed multiple times. In particular, in 2010, Shigeru Kondo computed one trillion decimal digits of the square root of two [13]. At that time, only the number π had been computed with greater precision (five trillion decimal digits). The modern relevance of this computational task is explained both by the desire to empirically confirm the pseudorandomness of the digit sequence of the root and by the wide range of applications for pseudorandom numbers, particularly in cryptography.
In addition to pseudorandomness, the digit sequence of the square root of a prime number has two other important features that make such sequences valuable from the perspective of modern cryptography. The first feature is that the digit sequence of the square root of a prime number (according to the hypothesis) is non-periodic. Therefore, such sequences of digits (or bits) can be used in stream ciphers for encrypting large volumes of information, including images, video, and audio files. The second feature is that the chosen prime number, as well as the digit number from which the "refinement" of the root value starts, can serve as secret parameters (a key) for a pseudorandom number generator based on computing the square root of a prime number.
This work will demonstrate an efficient method for constructing a non-periodic pseudorandom number generator based on computing the square root of a prime number. We will review some computational methods traditionally used for calculating square roots. We will also analyze these methods in terms of their suitability for use in a pseudorandom number generator (PRNG).
The Babylonian method. For the purpose of calculating the square root of two, the ancient Babylonian method for computing square roots is often used [10, 14, 15]. It is based on the following principle:
2 a +
n a
an+1= 2 n = a2n + a1n . (
The more repetitions in the algorithm (that is, the more iterations are performed and the larger “n” becomes), the better the approximation of the square root of two. Each iteration approximately doubles the number of correct digits.
The long division method for calculating the square root. This method used to be taught in schools. The advantage of this method is that at each step of the algorithm, one additional correct digit of the result is obtained [16], which also becomes the next digit of the pseudorandom sequence. The disadvantages of the method are that it is not systematic: at each step, the method’s parameters must be selected manually. In addition, the remainder at each subsequent step of the algorithm can be twice as long as the previous remainder. Therefore, this method is poorly suited for the automated calculation of a large number of root digits, which is required for generating pseudorandom sequences.
Method of calculating the square root via Taylor series expansion:
√1+x =n∑∞=0 ( 1−(2−n1))2((n2!n)2)(!4n ) x n =1+ 21 x − 81 x 2+ 116 x 3− 1258 x 4+... . (
Method of arithmetic extraction of the square root. For square numbers, the following rule applies [15] 1 = 12, 1 + 3 = 22, 1 + 3 + 5 = 32, and so on.
That is, the integer part of the square root of a number can be determined by successively subtracting all odd numbers from it until the remainder becomes zero or is less than the next odd number to be subtracted. The result (the integer part of the root) is the number of performed actions (subtractions). For example, 9 − 1 = 8, 8 − 3 = 5, 5 − 5 = 0.
Three steps were performed, so the square root of 9 is 3.
The disadvantage of this method of calculation is that as a result of its application, only the integer part of the result can be obtained. At the same time, this method is useful for obtaining a rough initial approximation of the root.
The iterative analytical algorithm (Heron's iterative formula). This is a popular and very ancient iterative algorithm [17], which allows refining the solution using the formula: { x n+1=21 ( x +a ) ,
n x n
x 0=a ,
(
n →∞
The method converges quickly: each iteration approximately doubles the number of correctly computed digits of the result. At the same time, the method involves complex operations, including division.
Numerical methods of approximate square root calculation. These methods [18] include, in particular, the bisection method, the secant method, the tangent method (Newton's method), and others. Most of these methods (except for the bisection method) do not allow for the computation of the square root “digit by digit.”
To compute square roots, specialized function transformations can also be used, for example, number-to-impulse transformations based on classical digital converters [18–20].
For use in PRNGs (pseudorandom number generators), most of the listed methods are unsuitable. This is due to two reasons. First, a PRNG typically needs to generate a long sequence of pseudorandom bits. When constructing such a generator based on the calculation of the square root of a prime number, this means that a large number of digits of the square root need to be computed. Moreover, each subsequent digit (bit) of the result must be computed precisely. Otherwise, the pseudorandomness property of the generated sequence may be lost. Additionally, the digits of the square root, which become bits of the pseudorandom sequence and can be used further in fast stream ciphers, must be computed quickly.
Thus, for use in a PRNG based on the square root calculator of a prime number, a fast and accurate “digit-by-digit” calculator is suitable. Accordingly, various methods for rough estimation of the square root value are only suitable for calculating the initial approximation. Methods such as columnar calculation and most of the approximate numerical methods (Heron's method, secant, tangent, and others) are also poorly suited. The main reason for their unsuitability in building a PRNG is the high complexity of computational operations, which increases with the number of computed digits. At the same time, it is worth noting that the columnar calculation method allows for the "digit-by-digit" computation of the result.
Considering the aforementioned application characteristics, the bisection method, or the method of bisections, is convenient for constructing a PRNG calculator. This method involves relatively simple computational operations. It has slow convergence, but it is fast and, under certain conditions, can be converted into a “digit-by-digit” method. In terms of performance, for a PRNG, the speed of generating the exact value of the next bit in the sequence is more important than the overall speed of generating the entire sequence without guaranteeing the accuracy of individual bits.
Let us formulate an observation regarding the bisection method that makes it possible to transform this method into a “digit-by-digit” square root calculation method.
If the width of the initial approximation interval in the bisection method (the interval in which the root of the nonlinear equation x2 = p is localized) equals an exact power of two, then at each step of the bisection method we obtain the next correct bit of the square root result.
Thus, if the formulated requirements for the initial approximation of the root are met, we can construct an algorithm for calculating the square root using the “digit-by-digit” method.
Therefore, the bisection method can be used to construct a pseudorandom number generator based on computing the square root of a prime number. Compared to other square root calculation methods, the bisection method is characterized by lower computational complexity, although it often has slower convergence. At the same time, the bisection method allows for the selection of an initial approximation that enables “bit-by-bit” computation of the square root, with each step of the algorithm yielding the exact value of the next bit of the result – an essential requirement when generating a pseudorandom bit sequence.
Another important characteristic of a pseudorandom number generator is its speed. The low complexity of the basic operations in the bisection method can ensure this performance characteristic. This is why the bisection algorithm is well-suited for computing the square root of large numbers. At the same time, when using a square root calculator to construct a pseudorandom number generator, a number of improvements to the bisection method can be proposed, which would significantly reduce the computational effort required. The essence of the proposed improvements is as follows: 1 The width of the initial approximation interval must be an exact (positive or negative) power of two. This allows for the precise computation of the next bit of the result at each step of the algorithm. Furthermore, as will be shown later, this makes it possible in the bisection algorithm to eliminate the need for monitoring the right boundary of the root localization interval, as well as to compute the midpoint of the interval by simply appending a one to the next bit. 2 When generating a pseudorandom sequence, which in the case of using a square root calculator of a prime number, is non-periodic—we can begin the generation from any bit. In doing so, it is necessary to provide an appropriate initial approximation of the root, i.e., the position of point a within the root localization interval (see Fig. 2). The width of the root localization interval should be chosen according to the requirements of point 1. As will be shown below, this allows for a significant simplification of the computation of root localization conditions. 3 For clarity and unambiguity in the further formal exposition, we choose the initial approximation of the root (the position of point a in the localization interval (see Fig. 2)) to be equal to the integer part of the root value.
In doing so, and in accordance with point 1, it is assumed that the right boundary of the root lo calization interval (point b) is located one unit away from point a.
We develop the generator’s operating equation based on the bisection method, taking into account the proposed improvements to the method. We need to compute the value of x, the square root of a prime number p.
x =√ p . (
To do this, we apply the bisection method, which we use to refine the initial approximation of the root of a nonlinear quadratic equation.
x 2− p =0. (
As the initial approximation x0 (the left boundary of the root localization interval in the
bisection method), we choose the integer part of x is the greatest integer whose square is less than
the number p. Obviously, at the initial approximation point, the value of the function (
( x c )2=y c =( x 0+2−1 )2=x 20+2 x 0⋅2−1+2−2=x 20+x 0+2−2=y 0+x 0+2−2 .
Next, we compare the computed yc with p. If yc < p, we set x1 = xc, y1 = yc.
(
Otherwise x1 = x0, y1 = y0. We then proceed further, and at the ith step of the algorithm, we
obtain:
( x c )2=y c =( x i−1+2−i )2=x i2−1+2−i+1 x i−1+2−2i =y i−1+2−i+1 x i−1+2−2i .
(
We again compare with p, and based on the result of the comparison, we determine the value of the next bit of the result. We continue in a similar manner.
Analyzing expression (
Next, the calculated number is compared with , and based on the comparison results, new values of xi and yi are established. The new value xi is set by appending either a zero or a one (the newly calculated correct bit!) to the next lower bit of the result. Thus, if we do not take into account simple operations such as bit writing, shifting, and reassignment, the proposed algorithm requires only one addition operation per correct bit of the result.
Based on the proposed operating principle of the generator and the derived operating equation of
its calculator (
The structure of the developed algorithm is presented in Fig. 3. The following notations are used
in the structure of the algorithm: x0 and y0 are initial approximations of the result x and its square;
pp is a given prime number; s is a number of bits in the integer part of the result; yy is a
intermediate value of the square of the result, calculated according to (
The developed algorithm (Fig. 3) provides for the generation of a 20,000-bit sequence for the
purpose of further analysis of the statistical properties of the generated sequence in accordance
with FIPS 140 standard. Therefore, the values x, y, and yy, which are large numbers, appear as bit
arrays in the algorithm shown in Fig. 3. Taking into account the term 2–2i added to y when
calculating yy according to (
In the proposed algorithm (Fig. 3), the main loop generates 20,000 bits of the square root of the
given prime number pp. To do this, according to (
In both cases, the increment of x for computing the next bit is halved, and we proceed to the next iteration of the algorithm.
The FIPS 140 standard defines four statistical randomness tests: the monobit test, the block test (poker test), the runs test, and the long runs test. Each test defines thresholds for acceptable statistical parameters. A separate bit sequence of length 20,000 generated by the PRNG is tested using all four tests. If any test fails, the generator is considered to have failed the entire test suite.
Monobit test. The essence of this test lies in counting the number of zeros and ones in the generated bit sequence of a given length (in this standard, the sequence length is 20,000 bits). Let n1 and n2 denote the number of zeros and ones in the sequence x, respectively. If the sequence is random, the values of n1 and n2 must satisfy the condition 9654 < n1 (n2) < 10346.
The structure of the developed monobit test algorithm is shown in Fig. 4.
k = n ≥ 5⋅( 2m ) . (
m
The sequence is divided into non-overlapping subsequences of length m = 2, 3, … . Let be the
number of occurrences of the ith type of subsequence of length m. The block test determines
whether the subsequences of length m appear approximately the expected number of times in the
sequence x that is, each subsequence should occur approximately equally often, as would be
expected in a truly random sequence. To apply the criterion, the following parameter is computed:
2m 2m
X 3= ( ∑ ni2 )−k , (
k i=1 which follows a distribution close to the χ2 with 2m – 1 degrees of freedom. The statistical parameter defined by the equation is calculated for m = 4. The statistic must satisfy the following condition 1.03 < X3 < 57.4.
The structure of the developed block test algorithm is shown in Fig. 5.
Here, blok is a four-bit block of the generated sequence, the array kblok accumulates the number of blocks of each type (by index), and Sub is the next generated bit.
Runs test. A run is defined as a sequence of identical symbols—either ones or zeros. The essence of the test is to count the number of runs of lengths 1, 2, 3, 4, 5, and 6 in the tested sequence of a given length (runs longer than 6 elements are treated as runs of length 6). If the sequence is random, the number of runs of each length should fall within the following intervals (Table 1). That is, as the run length increases by one, the number of runs approximately halves.
Long run length test. The essence of this test lies in verifying the maximum length of a run of identical elements (ones or zeros). If the sequence is random, the maximum run length must not exceed 34.
The structure of the developed combined algorithm for the runs test and the long run length test is shown in Fig. 6.
Here, SS denotes the run length (not exceeding 6), S is the absolute length of the run, Sub is the current generated bit, and Sub0 is the previously generated bit. The arrays serii_1 and serii_0 accumulate the number of runs of the corresponding (indexed) length. max stores the maximum run length.
Analyzing the proposed algorithm (Fig. 3), we conclude that generating a single bit of the
pseudorandom sequence x requires one addition, one comparison, and, optionally, one
reassignment. In contrast, in the classical bisection algorithm applied to our function (
Thus, the proposed algorithm, compared to the classical one, saves one multiplication per bit of the result. Considering that the approximate complexity of the proposed algorithm is one addition per bit of the result, this gain is significant, especially in view of the lengths of bit sequences that must be generated in stream ciphers using PRNGs.
Based on the proposed algorithm for the operation of the PRNG on a square root calculator of prime numbers (Fig. 3), as well as the developed PRNG testing algorithms according to the FIPS 140 standard (Figs. 4-6), a software implementation of the generator based on the square root calculator of a prime number was developed. The implementation enables the generation of a pseudorandom sequence in accordance with the proposed method for computing the square root of a prime number. It also provides the capability to investigate the statistical properties of the generator.
In the process of studying the statistical properties of the developed generator, a sequence of 20,000 pseudorandom bits was generated using its software model. During this process, the generated sequence was tested for compliance with the requirements of the FIPS 140 standard. The results of the statistical testing of the generator for three small prime numbers are summarized in the Table 2.
The results of the runs test for ones are presented in the upper row, and for zeros in the lower row.
The paper presents the results of the development and investigation of the structure of a pseudorandom number generator based on a square root calculator of a prime number. The square root of a prime number is an irrational number. Therefore, the sequence of its digits hypothetically forms a non-periodic pseudorandom sequence. An improvement to the bisection method is proposed in order to enable its application in the PRNG based on the square root calculator of a √3 √17 √31
10005
Block test 10 18 24 prime number. An algorithm and software implementation of the PRNG based on the square root calculator of a prime number have been developed. The statistical characteristics of the PRNG based on the improved square root calculator have been investigated. The results of the conducted research show that the application of the improved bisection method allows a significant enhancement in performance due to the reduction of computational workload per multiplication during each iteration. In the context of the PRNG built upon such a method, this means that computing a single bit of the pseudorandom sequence requires only one addition operation. The evaluations of the statistical characteristics of the developed generator confirm that the quality of the pseudorandom sequences it generates meets the requirements of the FIPS 140 standard. Declaration on Generative AI While preparing this work, the authors used the AI programs Grammarly Pro to correct text grammar and Strike Plagiarism to search for possible plagiarism. After using this tool, the authors reviewed and edited the content as needed and took full responsibility for the publication’s content. [16] C. Baumann, Playing with the square root. A practical study, ver. 1.5, 2024, 1–54. https://computarium.lcd.lu/literature/COMPUTARIUM_CREW/BAUMANN/report_squareroot _1.5.pdf [17] A. Ralston, P. Rabinowitz, A first course in numerical analysis, 2nd ed., McGraw-Hill, 1978. [18] A. Horpenyuk. V. Dudykevych, N. Luzhetska, Conveyor sine-cosine pulse-number functional converter, Autom. Meas. Control 639 (2009) 94–101. [In Ukrainian]. [19] P. Montuschi, M. Mezzalama, Survey of square rooting algorithms, IEE Proc. E Comput. Digit.
Tech. 137(
Comput. 4(