Some Applications of Binary Lunar Arithmetic Van Vinh Dang Nataliya Dodonova Mikhail Dodonov Hochiminh city University of Samara National Research University Samara National Research University Technology Samara, Russia Samara, Russia Hochiminh city, Vietnam ndodonova@bk.ru dodonoff@mail.ru dangvvinh@hcmut.edu.vn Svetlana Korabelshchikova Northern (Arctic) Federal University named after M.V. Lomonosov Arkhangelsk, Russia s.korabelsschikova@narfu.ru Abstract—In general, we formulate the problem of extracting n-th order roots from a language as follows: for a 6 1 7 9 given language A and a given nN it is required to find all the X languages B, such that A = Bn. This theoretical problem is 3 4 8 closely related to the practical task of decoding messages, where 6 1 7 8 it is necessary to find a partition of the encoded message into 4 1 4 4 elementary codes that correspond to certain characters of the + original alphabet. We previously found a solution to the 3 1 3 3 problem of extracting n-th order roots for languages of a special 3 4 6 4 7 8 kind, which is containing all the possible words of the length from nn1 to nn2 (n1  n2). We reduced the problem under consideration to a knapsack problem and solved it by the You can learn more about the features of lunar arithmetic method of software implementation of the algorithms proposed in [1]. We are most interested in the binary case when in the article. We found out that the number of roots depends on operations on numbers are performed according to the rules the values of n and k, where k is the cardinal number of the set formulated above, but the numbers belong to the set {0, 1}. {n1, n1+1,..., n2}. We obtained quantitative estimates of the In the past, in [2, 3], we considered the problem of number of n-th power roots for different values of n and k. For n = 2, the sequence of the number of square roots from the extracting all the roots from special kind of languages. In language coincid with the sequence published on the website of general, the problem of extracting the n-th root from a the online encyclopedia of integer sequences http://oeis.org/ language can be formulated as follows: for a given language A191701. In binary lunar arithmetic, this sequence is the A and given nN, it is required to find all languages B such number of binary numbers x of length k such that x2 has no that A = Bn. In this case, we call the language В the n-th root zeros. In the article, we established and theoretically proved the of the language А. This theoretical problem is closely related correspondence between operations in binary lunar arithmetic to the practical problem of decoding messages, where it is and in the ring of polynomials with integer coefficients. Based necessary to find the division of the encoded message into on the established correspondence, we developed algorithms that allows us to solve both the special problem of finding roots elementary codes corresponding to the characters of the from a language and the more general knapsack problem using original alphabet. operations in binary lunar arithmetic. We compared the Let us introduce the necessary notations. Let М be a finite software implementation of the proposed algorithm with the subset of the set of natural numbers, let  - be an alphabet, well-known classical alternative solutions to the knapsack possibly infinite. We consider languages of the form (М) problem. Using the discrete Fourier transform, we were able to containing all the i-digit long words over the alphabet , improve the asymptotic complexity of the original algorithm. where iМ. We call the set М, defining the language (М), - Keywords—dismal arithmetic, binary lunar arithmetic, the set of indices. The solution to the problem of extracting knapsack problem all the roots was obtained for languages А=[t1;t2], containing all the words of length from t1 to t2 (t1 t2). Let us I. INTRODUCTION show two examples. American scientists D. Applegate, M. Lebrun, and N. J. Example 1. Let  be an arbitrary alphabet. We can A. Sloane introduced the concept of “lunar arithmetic” in [1], extract 5 square roots from the language А=[2;14] with sets and originally they used the term “dismal arithmetic”, of indices {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 6, 7}, {1, 2, 4, 5, 6, subsequently replacing it with a less pessimistic “lunar 7}, {1, 2, 4, 6, 7} and {1, 2, 3, 5, 6, 7}. arithmetic”. Let’s consider, for example, the language B=(М), where In the so-called lunar arithmetic, we replace the addition М={1, 2, 4, 6, 7}. We can show, that B2=A. The and multiplication of numbers by the operations of multiplicative operation here is concatenation. Since calculating the maximum and minimum, respectively. For language B contains all 1-digit long words, language В2 example, 2 + 7 = 7, and 27=2. With multi-digit numbers, the contains concatenations of 1-digit long words, that is, all 2- addition operation is performed by columns, i.e., a maximum digit long words. Similarly, language В2 contains all words of is selected in each column. For instance 6179 + 348 = 6379. length 4, 8, 12, and 14. We can get all the 3-digit long words The rule for multiplication of two multi-digit numbers is that by concatenating words of length 1 and 2 (1, 2М), we can the first number multiplies every digit of the second number get all the 5-digit long words by concatenating words of and then the results are added together, i.e., we select the length 1 and 4 (1, 4М), and so on for the remaining natural maximum in each digit (column): numbers from the interval [2, 14]. Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) Data Science Example 2. In binary lunar arithmetic, this sequence is the number of Let us find all the cube roots from the language binary numbers x of length k such that x2 has no zeros. In this А=[27;42]. paper, we will establish the reason for this coincidence, Obviously, the set M1={9, 10, 11, 12, 13, 14} defines a interpret our results in terms of lunar arithmetic, and apply cubic root В=[9;14] from А. Similarly to the example 1, we the established relation to solve the knapsack problem. can verify that the set М2 = {9, 10, 13, 14} defines another cube root from the language А. Therefore, the roots will be II. BINARY LUNAR ARITHMETIC AND OPERATIONS ON POLYNOMIALS also two other languages with sets of indices M3={9, 10, 11, 13, 14} and M4={9, 10, 12, 13, 14}. Let the initial set be {0, 1}. In the binary case, the lunar In general, the n–th root from the language А=[t1;t2] is addition (finding a maximum) corresponds to the disjunction, extracted successfully if and only if t1 and t2 are divisible by and the multiplication (finding a minimum) corresponds to n. Let M be a subset of the set of natural numbers the conjunction. Let us consider lunar operations over multi- {n1, n1 + 1, …, n2}, where n1=t1/n, n2=t2/n. The language digit binary numbers. When adding in each column, select the B=(М), containing all words of length aj, ajМ, is an n‒th maximum: 1011 + 101 = 1111. When multiplying, we follow root from the language А if and only if the condition is the rule of multi-digit numbers multiplication in the lunar satisfied: arithmetic shown above. Thus, 1011 101= 101111 (when summing by columns we 1 0 1 1 find the maximum). X 1 0 1 We see that the original vector 1011, when multiplied by 1 0 1 1 1, remains unchanged, shifting to the left by the position of 0 0 0 0 this bit. This multiplication is similar to a multiplication in + 1 0 1 1 the ring Z[x] of polynomials. If the original polynomial f(x) is multiplied by xi, then all its coefficients will remain 1 0 1 1 1 1 unchanged, only i zeros will be added to the right, which (i) (n  n1  i  n  n2  i = a1 + a2 + … + an), (1) corresponds to a shift of the coefficient vector f(x) by i where a1, a2, …, an are some elements from М (not positions to the left. We associate the binary vector 1011 with necessarily different). the polynomial x3+x+1 and vector 101 with the polynomial The task of checking condition (1) is equivalent to the x2+1. We get: specific case of the unlimited knapsack problem. We can (x3+x+1)1= x3+x+1=1011 solve this problem by the method of dynamic programming, (x +x+1) x2= x5+x3+ x2=101100 3 finding the answer in polynomial time. Condition (1) is Adding the coefficients at the equal powers, we have obviously satisfied for the set {n1, n1 + 1, …, n2} and x5+2x3+x2+x+1=102111. In the polynomial ring, when corresponds to the trivial root В=[n1,n2], containing all calculating the coefficients at the equal power, we perform words of length from n1 to n2. Verification of condition (1) the usual addition, and in the lunar binary arithmetic if there for other subsets of the set {n1, n1 + 1, …, n2} was carried out is 1 in the column, the result is 1, if all the numbers are zeros, by the method of a software implementation of well-known the result is 0. Thus, the following theorem is true. algorithms for solving the unlimited knapsack problem. Theorem 1. Let us compare the polynomial Table 1 shows the results of the program, i.e., the number of anxn+an-1xn-1+…+a1x+a0 n-th roots from languages of the form А=[t1;t2] for some n to the binary vector (an,an-1,…,a1,a0). When the mapping is and k (k = n2 – n1 + 1). For k from 1 to 3, the values are 1. set in this way, operations in binary lunar arithmetic correspond to operations on polynomials in the ring Z[x] with TABLE I. THE NUMBERS OF N‒TH ROOTS IN DIFFERENT K subsequent replacement of non-zero coefficients by 1. Proof. n \k 4 5 6 7 8 9 10 11 12 13 14 Without loss of generality, we consider two binary 2 1 2 3 5 9 15 28 50 95 174 337 vectors a=(an,an-1,…,a1,a0) and b=(bn,bn-1,…,b1,b0) of the same length. Otherwise, we can add to the shorter vector 3 1 2 4 7 13 25 49 95 185 365 721 zeros on the left. Then a+b=(an bn, an-1 bn-1,…,a1 b1, a0 4 1 2 4 8 15 29 57 113 225 447 889 b0) and 0 will be in the i-th position if and only if ai= bi=0. On the other hand, for the polynomials a(x)=anxn+an-1xn- 5 1 2 4 8 16 31 61 121 241 481 961 1 +…+a1x+a0 and b(x)=bnxn+bn-1xn-1+…+b1x+b0, we have a(x)+ b(x)= (an+ bn) xn+(an-1+bn-1 )xn-1+…+ (a1+b1 )x+a0+b0 6 1 2 4 8 16 32 63 125 249 497 993 Since the initial vectors a and b are binary, the coefficients of the polynomial a(x)+ b(x) belong to the set {0,1,2}, moreover 7 1 2 4 8 16 32 64 127 253 505 1009 the coefficient xi equals 0 if and only if ai= bi=0. For this reason, after replacing all nonzero coefficients by 1, the We found the sequence for n = 2 on the website coefficient vector of the polynomial a(x)+ b(x) is equal to the http://oeis.org/A191701, which, in turn, refers to the work vector a+b. [1]. D. Applegate, M. Lebrun and N. J. A. Sloane obtained The corresponding results for multiplication can be this sequence for k from 1 to 41: derived similarly. 1, 1, 1, 1, 2, 3, 5, 9, 15, 28, 50, 95, 174, 337, 637, 1231, 2373, 4618, 8974, 17567, 34387, 67561, ... (2) VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 76 Data Science III. BINARY LUNAR ARITHMETIC AND THE PROBLEM OF is a n‒th root from the language А=[nn1;nn2] if and only if FINDING ALL THE ROOTS OF THE LANGUAGE in binary lunar arithmetic n has no zeros. Next, we interpret the content of the sequence (1). The Theorem 2 provides another method to verify whether According to the author’s terminology, this sequence a subset М is a set of indices for some root from a language of represents the number of k-digit long binary vectors. The the form А=[t1;t2]. lunar squares of these vectors consist of all ones. The lunar IV. APPLICATION OF LUNAR ARITHMETIC TO SOLVING square is the result of multiplying the vector by itself. THE KNAPSACK PROBLEM Example 3. Lunar squares of the following 5 vectors with the same length k = 7: 1111111, 1111011, 1101111, 1101011 The classical knapsack problem in general can be and 1110111 are 1111111111111=1(13), therefore, the seventh formulate as follows: given a set of items, each with a weight term in the sequence (1) is 5. For all other 7-digit long binary and a value, select a certain subset of objects so that we get vectors, the lunar square will contain zeros. maximum total cost, subject to the restrictions on the total Let us move to the polynomial operations. weight. For instance, we associate the polynomial The unlimited knapsack problem is a generalization of the a(x)=x6 + x5 + х3 + х + 1 with the fourth vector a=1101011. classical problem when any item can be taken any number of After multiplying the polynomial with itself, we get times. We consider a special case of this problem when the (x6 + x5 + х3 + х + 1) (x6 + x5 + х3 + х + 1) = value of the item is a natural number, and equal to its weight. =c12x12 + c11x11 +c10x10 + c9x9 + c8x8 + c7x7 + c6x6 + Therefore, we may not take into account the cost of items, but + c5x5 + c4x4 + c3x3 + c2x2 + c1x + c0. only their weight. We also add the condition that the taken Following the rule of theorem 1, we consider all non-zero items must be equal exactly M. We formulate this problem in coefficients equal to 1. mathematical language. c0= a0 a0=1, The knapsack problem 1. Given N items. The capacity c1= a0 a1+ a1 a0=1+1=1, of the knapsack is W, M - the number of items to be taken, and the natural numbers w1, w2, …, wN. - are weights c2= a0 a2+ a1 a1+ a2 a0=0+1+0=1, and so on. corresponding to the items. Find a set of values x1, x2, …, xN, We get c0= c1=…= c12=1. where xi is the number of taken items of a certain type, and The power xi can be represented as the sum of the powers such that: of the factors, that is as a sum of powers of a polynomial a(x), 1. x1 w1 + … + xN wN ≤ W; if and only if this power is present in the product a(x)a(x). For some, not necessarily different, j and k we obtain i=j+k, 2. x1 + … + xN = M; where j, k{0, 1, 3, 5, 6}. 3. x1 w1 + … + xN wN has a maximum. In the polynomial a(x)a(x), all the coefficients ci are nonzero, hence any i from 0 to 12 can be represented as the Note. All the weights of objects are different. If there are sum of two (not necessarily different) numbers from {0, any objects with the same weight, then we will always take 1, 3, 5, 6}. from them only some specific one. Such an assumption will Let us recall that the problem of extracting all the roots not change anything in problem 1, since any item can be from the language А=[t1;t2] is reduced to the same question. selected any number of times. In the example 1 we extracted 5 square roots from the Algorithm language А=[2;14] with the sets of indices: Step 1. Create a polynomial 𝑦 = 𝑥 𝑤1 + 𝑥 𝑤2 + ⋯ + 𝑥 𝑤𝑁 {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4, 6, 7}, {1, 2, 4, 5, 6, 7}, according to the selected set of weights ŵ= {w1, w2, …, wN}. {1, 2, 4, 6, 7} and {1, 2, 3, 5, 6, 7}. We associate these Step 2. Associate the polynomial y with the binary vector subsets of the set {1, 2, 3, 4, 5, 6, 7} to its binary u of its coefficients. Then, in the vector u, for all ui, the characteristic vector (1, 2, …, 7), so we obtain 5 binary following condition holds ui=1, if i ŵ; otherwise ui=0. 7-digit long vectors from the example 3. Step 3. Raise the vector u to the power M in the lunar Let us interpret the results obtained in Table 1 in terms of binary arithmetic. We get the binary vector z = uM. lunar arithmetic. In the vector z, all nonzero zk denote that there exists a set It is not difficult to verify that the second sequence of the of exactly M objects, not necessarily different, whose sum of number of cubic roots from languages of the form А=[t1;t2] weights is k. This statement justifies the next step. coincides with the number of k-digit long binary numbers, Step 4. Choose the maximum number k satisfying the whose lunar cubes consist of ones. conditions: k W and zk≠0. In particular, for k = 6, the lunar cubes of four vectors: Step 5. Find the linear combination methodx1 w1 + … + 110011, 111011, 110111, and 111111 give a unit vector (it xN wN=k using the backstepping. will be 16 -digit long). These vectors are characteristic Example 4. Given 4 items with weights 2, 3, 6, 7, and vectors for the sets of indices from Example 2. the capacity of the knapsack W=17. Find exactly 3 items. In the general, the following theorem is true. Step 1. Create the polynomial 𝑦 = 𝑥 2 + 𝑥 3 + 𝑥 6 + 𝑥 7 . Theorem 2. Let  be an arbitrary alphabet. Let k be the Step 2. Associate the polynomial y with the binary vector cardinal number of the set {n1, n1+1,..., n2}, i.e. u=(11001100) of its coefficients. k = n2 – n1 + 1. Let M be a subset of the set Step 3. Compute u3 in the lunar arithmetic, we obtain: {n1, n1 + 1, …, n2}, and  = (1, 2, …, k) be the binary u2= (111011101110000), or (by the theorem 1) 𝑦 2 = characteristic vector of the subset M. The language В=(М) 𝑥 + 𝑥 13 + 𝑥 12 + 𝑥 10 + 𝑥 9 + 𝑥 8 + 𝑥 6 + 𝑥 5 +𝑥 4 . 14 u3= (111111111111111000000) = (1 1606). Step 4. k=17. VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 77 Data Science Step 5. 17=10+7; 10=7+3. Hence, 17=7+3+7, so that we - Solution E is a solution using the product of polynomials need to choose 2 items weighing 7 and one item weighing 3. in lunar arithmetic. The product of polynomials is produced There is a second solution 17=14+3; 14=7+7. Hence using the fast Fourier transform. The M-th power of a 17=7+7+3, which, in fact, coincides with the first solution. polynomial was raised using binary exponentiation. The We evaluate the asymptotic complexity of this algorithm. parallel FFT algorithm was used [6]. Calculations are made Let us denote by wmax = max{ wi | 1 ≤ i ≤ N} the weight of on 2, 4, or 8 processors. the heaviest item, that is, the maximum power of the Testing was conducted on a cluster of CAFU, which has polynomial y. Then wmax ∙ M is the maximum power of the the following characteristics: polynomial yM=z. The latter operation can be implemented in - 20 computing nodes; a naive way, which involves sequentially calculating the - on each node there are 2 ten-core Intel Xeon processors powers of y from 2 to M, or using the “binary power raising” and 64 GB of RAM; technique, which allows raising any number to the power of - additionally installed mathematical coprocessors Intel n in O (log n) multiplications instead of n multiplications in Xeon Phi 5110P on the eighth node; the usual sequential multiplication. Using this technique, the - The internal computer network for computing: asymptotic complexity of this algorithm is Infiniband 56 Gb / s; O ((wmax ∙ M )2 ∙ log (M )), where ( wmax ∙ M )2 is the - FEFS network file system (Fujitsu Exabyte File System) algorithmic complexity of multiplying two polynomials, with a capacity of more than 50 TB and a bandwidth of 1.67 log M is the algorithmic complexity of binary GB / s (13.36 GB / s); exponentiation. - cluster performance on the CPU in the LINPACK test We can use the Fast Fourier Transform algorithm (FFT) 8.02 Tflops; on CPU + Xeon Phi 7.68 Tflops, cumulative 15.7 [4, 5] to multiply two polynomials. To multiply two Tflops; polynomials in binary lunar arithmetic, based on Theorem 1, The results of the execution time of the programs are it suffices to multiply the polynomials over the standard presented in table 2. complex field and, after obtaining the resulting polynomial, change the coefficients that are greater than one by one. TABLE II. TESTING RESULTS Multiplication of polynomials in binary lunar arithmetic using T Solution Solutio Solutio Solut Solut Solut Soluti FFT has asymptotic complexity O (wmax · log(wmax)). Thus, it es A, n B, n C, ion ion ion on turned out to improve the asymptotic complexity of the t seconds. second second D, E2p E4p E 8 pr original algorithm to O (wmax · log(wmax) · log(M)). We also s. s seco roces roces ocess note that FFT can be implemented using the parallel algorithm nds sors, sors, ors, from [6]. seco seco secon nds nds ds V. COMPARATIVE ANALYSIS OF SOLUTIONS TO THE 1 46.780 0.340 14.800 0.18 0.15 0.13 0.131 0 3 7 KNAPSACK PROBLEM 2 187.260 1.760 62.300 0.38 0.31 0.27 0.264 A comparative analysis of the program execution time 0 9 5 among various solutions to the problem 1 on the knapsack 3 192.670 1.250 32.990 0.37 0.31 0.27 0.265 0 6 7 problem was carried out by the 2nd year master specialized 4 772.610 5.610 137.33 0.83 0.65 0.58 0.550 in 01.04.02 “Applied Mathematics and Computer Science” 0 0 7 5 A. I. Chesnokov. Testing was carried out on computing M-th 5 445.530 1.820 58.310 1.00 0.65 0.57 0.540 power of random polynomials of power N. There are the 0 4 1 6 1793.23 8.160 268.72 1.90 1.47 1.24 1.244 restrictions on N and M in experiments: 0 0 0 6 6 Test 1 – N = 500, M = 500; 7 779.010 3.280 77.380 0.91 0.68 0.57 0.566 Test 2 – N = 500, M = 1000; 0 9 6 Test 3 – N = 1000, M = 500; 8 3133.81 13.120 322.01 1.94 1.51 1.30 1.241 Test 4 – N = 1000, M = 1000; 0 0 0 2 1 Test 5 – N = 1500, M = 500; Test 6 – N = 1500, M = 1000; According to table 2, we can make a conclusion that the Test 7 – N = 2000, M = 500; solution to problem 1 using FFT in binary lunar arithmetic Test 8 – N = 2000, M = 1000. and binary exponentiation is faster than the other solutions. There were 7 different solutions to the knapsack problem The speed of the parallel FFT algorithm in all the tests 1 [7,8]. increases noticeable, especially with the increasing number - Solution A is a solution using dynamic programming; of threads (in some cases, significantly). - Solution B is a solution using dynamic programming VI. CONCLUSION using bitmasks; - Solution C is a solution using the product of polynomials Let us summarize the results. In the theoretical part of the in lunar arithmetic. The product of polynomials is computed work, we established a relation between operations in binary using the fast Fourier transform. The M-th power of a lunar arithmetic and in the ring of polynomials with integer polynomial is computed in a naive way; coefficients (Theorem 1). We also created an association - Solution D is a solution using the product of polynomials between binary numbers x of length k for which xn does not in lunar arithmetic. The product of polynomials is produced contain zeros in binary lunar arithmetic and sets of indices of using the fast Fourier transform. The M-th power of a roots of the n-th power from a language of a special form polynomial is computed using binary exponentiation; (Theorem 2). A generalization of the problem of extracting the n-th root from a language of a special kind is a VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 78 Data Science mathematical model of a special case of the problem of an IX international conference Discrete models in the theory of control systems, pp. 116-118, 2015. unbounded knapsack problem (Problem 1). To solve this [3] B.F. Melnikov, S.Yu. Korabelshchikova and V.N. Dolgov, “On the problem, we developed an algorithm based on lunar binary task of extracting the root from the language,” International Journal of arithmetic. Open Information Technologies, vol. 7, no. 3, pp. 1-6, 2019. We made the software implementation of the proposed [4] G. Nussbaumer, “Fast Fourier Transform and convolution algorithms algorithm in several variants, using optimization methods of of computation,” Moscow: Radio and communications, 1985. calculations and parallel technologies. Table 2 gives us a [5] S.Yu. Korabel’shchikova and A.I. Chesnokov, “Lunar arithmetic chance to compare the solution obtained by the authors with algorithms and fast Fourier transform in a knapsack problem,” Heuristic Algorithms and Distributed Computing, vol. 2, no. 3, pp. 41- other known solutions (solution A and solution B) of the 49, 2015. unbounded knapsack problem. [6] V.V. Voevodin and Vl.V. Voevodin, ‘Parallel computing,” SPb.: The knapsack problem belongs to the class NP‒complete BHV-Petersburg, 2002. problems. This means that there is no polynomial algorithm [7] D. Pisinger, ”Knapsack problems,” 1995. to obtain the exact result (solution). The results presented in [8] S. Martelo and P. Toth, “Knapsack problems,” Wiley, 1990. table 2 demonstrate that, despite this pessimistic fact, in some [9] S.Yu. Korabel’shchikova and A.I. Chesnokov, “On the number of cases, a solution to such a problem can be obtained in different cyclic codes of a given length,” Vector science TSU, vol. 4, seconds. no. 26, pp. 25-26, 2013. The results obtained in this research can be applied to solve [10] S.Y. Korabelshchikova, L.V. Zyablitseva, B.F. Melnikov and S.V. Pivneva, “Linear codes and some their applications,” Journal of many problems related to the knapsack problem. In particular, Physics: Conference Series electronic edition, 012174, 2018. the problem of estimating the number of different cyclic codes [11] B.F. Mel’nicov, S.Yu. Korabel’shchikova, “Algorithms for with given parameters was solved in [9] using this method. computing the number of error-correcting codes of a general and Some additional algorithms were proposed in [10,11,12]. special form,” Informatization and communication, vol. 1, pp. 55-60, 2019. REFERENCES [12] V.M. Chernov, “Fibonacci, tribonacci, ..., hexanacci and parallel [1] D. Applegate, M. LeBrun and N.J.A. Sloane, “Dismal Arithmetic,” "error-free" machine arithmetic,” Computer Optics, vol. 43, no. 6, pp. Arxiv preprint: 1107.1130v2.pdf, 2011. 1072-1078, 2019. DOI: 10.18287/2412-6179-2019-43-6-1072-1078. [2] S.Yu. Korabel’shchikova, A.I. Chesnokov and A.G. Tutygin, “On primitive roots from languages of a special type,” Proceedings of the VI International Conference on "Information Technology and Nanotechnology" (ITNT-2020) 79