Method for Generating Pseudorandom Sequence Permutations Based on Linear Congruential Generator of

Abstract

  The results of the study of the graph of states of a linear congruential generator (LCG) are considered and theoretically substantiated. A model of a generalized graph of LCG states has been developed. It represents each connected component of the graph in the form of cycles equipped with tree products, allows classifying the types of connectivity components of the graph of LCG states and investigating the influence of parameters on its topology. A method for generating a pseudorandom sequence (PRS) of numbers based on the linear congruential method is presented. This method allows generating uniformly distributed numbers regardless of the topology of the graph of LCG states and, consequently, minimizing the time spent on choosing its parameters, and increasing the size of the space of their allowable values to achieve the maximum period. Computer implementation of the algorithm for generating PRS of permutations based on LCG with any type of graph of its states has allowed increasing the speed of the generator compared to the permutation generator using the modern Fisher-Yates algorithm.

Keywords

•  1  Pseudorandom sequence
• permutation
• shuffle
• random interleaver
• linear congruential generator
• graph of states
• monad
• topology
• monad graph

1. Introduction 

si  K  si1  C M where

K is the multiplier; C is the growth;

M is the module, K , C, s0  ZM .

Congruential sequence always forms repeating cycles [ 1 ].

LCGs are very sensitive to changes in parameters. Numerous works on the theory and application of congruential generators are aimed at choosing their parameters and assessing the quality of the obtained PRSs. Among them are both classical [ 1, 14-17 ] and modern works [18-22].

At the same time, despite the large number of studies on the choice of LCG parameters and experimental evaluation of its properties, most of them are aimed at improving the "randomness" of the formed sequence and do not take into account the structure of space of LCG states S .

Among the works devoted to the analysis of the structure of the space of LCG states, one of the main ones is the thorough scientific work of G. Marsaglia [23]. In addition, the work [24] is devoted to the development of the theory of PRS construction based on the LCG and LFSR.

The analysis of the simplest PRNGs, LCG and LFSR, shows their limitations due to the need to select parameters in order to ensure necessary PRS statistical properties. In particular, the allowable values of the generator parameters to ensure the maximum PRS period are shown in Table 1.

Table 1 

PRNG parameters to achieve the maximum PRS period 

Method 

Period 

Linear congruential  method [13] 

Method based on LFSR  [25‐27] 

Method for PRS  generating based on  concatenation of LCG  cycles [24] 

 

Method for PRS  generating based on  concatenation of LFSR  cycles [24] 

T  M   T  2n 1 

T  M   T  2n   Valid values of PRNG 

parameters   1)  Gcd С, М   1;  2)  K 1 p  0  for    simple  p : M p  0 ;  3) if  M 4  0  K 1 4  0     Generator polynomial  Gn  x   is primitive one 

Size of space of permissible  values of PRNG parameters  

  M   P ,  where  P  is the number of 

K  values that satisfy  conditions 2 and 3  

Corresponds to the number  of primitive polynomials   of  n  degree 

Gcd  K , M   1     M   M   Generator polynomial  Gn  x   generates a cyclic structure   of the graph of LFSR states 

Corresponds to the number 

of polynomials of  n  degree  that generate the cyclic  structure of the graph of 

LFSR states 

The purpose of the work is to generate PRS of permutations with high performance and necessary statistical properties without the need to select LCG parameters.

For the further study and analysis of PRNG construction based on sequential traversal of all vertices of the graph of LCG states, it is necessary to perform an in-depth study of the structure of the graph of LCG states, extended analysis of the influence of LCG parameters on the structure of its graph, and, consequently, to develop the method for generating PRS based on linear congruential method by sequentially traversing the contour of the graph of states of the generator.

2. Review of the literature 

To study and generalize the structure of the graph of LCG states, we shall explore the main approaches to forming graphs of states of PRS generating devices.

Cycle graphs 

A cycle graph [28], also known as a simply n -cycle [29], is a graph containing n nodes and consisting of a single cycle that passes through all its nodes. The cycle graph is denoted by Cn . The number of vertices in Cn is equal to the number of edges, each vertex has a power of 2, any vertex is incidental to two edges.

Cycle graphs are used, for example, to illustrate the structure of multiplicative groups M n (Figure 1). Such graphs are formed by creating numbered nodes, one for each  element of the surplus class, and constructing cycles obtained by calculating  i for i  1, 2,. Each edge of such a graph has a bidirectional character [28].  

Figure 1: Graphs for some small‐order multiplicative groups (from [30]) 

In all graphs of Figure 1 the node with   1 is highlighted because it is a zero cycle:  j   j

  1 for any j . Next, we shall use the same notation to represent zero cycles in the M graph of LCG states.

Note that in Figure 1 not all represented graphs are cycle graphs. This follows from the fact that multiplicative group by M module can be isomorphic to the product of several cyclic groups (for example, M 8  C2  C2 , and M15  C2  C4 ). In this case, the graph is a combination of several cycle graphs.

To visually represent the structure of the graph of LCG states, it is necessary to use an oriented cycle graph, an oriented version of the cycle graph, in which all arcs are directed in the same direction. 2.2.

Algebra of monads and topology of monad graphs 

This paragraph, as well as its name, is based on the V. I. Arnold works [31-32].

According to [31], a monad is a representation of a finite set in itself. The monad graph has all elements of this finite set as vertices, and oriented edges connect each element with its image.

In other words, a monad graph is an arbitrary finite oriented graph, from each vertex of which exactly one edge emerges. Iterations of the monad lead any vertex to a cycle attractor.

According to [31], each connected component of the monad graph is a forest of root-oriented root trees, the roots of which are connected by an oriented cycle (topologically circular) from the edges connecting the tree roots.

In other words, connected components of any monad are cycle attractors, which are equipped with root trees attached by their roots to each vertex of the cycle attractor [32]. The number of vertices of the cycle can be equal to 1. In this case, the whole component is one root tree.

Each connectivity component of the graph of any representation of a finite set contains one and only one cycle.

Let S be a finite group, and f : S  S representation transforms each of its elements s  S according to the expression: f  s   K  s  C M , where K is the multiplier; C is the growth; M is the module, K , C, s0  M .

In this paper, f : S  S representation will be called the monad of S group.

According to [31], the symbols O , An , Tm , En will denote the following oriented graphs: n  On = oriented cycle of n vertices;  An = connected graph of 2n vertices, which is a cycle of n length, equipped with n singleedge trees, which are included one in each of n vertices;  T2n = root tree with 2n vertices and n floors except the root, which branches binarially on 1,, n 1 floors; the root is considered to be the zero floor, and it also includes two edges: one is from itself and one is from a single vertex of the first floor;  En = root tree with n vertices, from each of which the edge leads directly to the root (so that E2  A1  T2 );  Dn = 4n -vertex graph, consisting of On cycle of n length, equipped in each of its vertices with three input edges (form together with this corresponding to the cycle vertex the root tree D  E4 ).

1

For example, graphs of monads for additive cyclic groups in the field n have the form shown in

According to [31], a monad that acts on the direct product X  Y component by component:  A  B x, y    Ax  By is called the A  B product of A and B monads that act on X and Y , respectively. The number of elements of a monad product is equal to the product of the number of elements of monad coefficients.

In [31] it is also shown that the graph of the monad product is the product of graph coefficients:  graph  A  B   graph A   graph  B / An  A1  On , Dn  D1  On .

Multiplying any root tree T by On equips n -cycle On with root trees of T type with roots at all points in the cycle.

3. Materials and methods 

In this section, we shall investigate the LCG topology and generalize the graph of its states to develop a method for generating permutation sequences. 3.1.

Graphs of linear congruential generator 

Examples of graphs of monads of S group for some LCG parameters are shown in Table 2.  

Table 2 

Oriented graphs of LCG states for some of its parameters 

LCG parameters 

M   K   C  

Graph of states 

LCG parameters 

M   K   C  

Graph of states  6  7  7  8  8  8  4  6  3  5  3  1  3  1  2  1  1  6  0 1 4 3 3 0 3 5 2 6 1 5 3 3 2 1 4 2 6 4 0 4 0 5 2 1 Group of  an ‐ vertex trees with  n floors   a  2 , dan  M    A group of cycles of  t length,  equipped in each of its vertices  with input edges  n 1 , and a  group of root trees with  n vertices, from each of which the  edge leads directly to the root  n  dt  k   M    A group of zero cycles with single‐ edge trees included in them,  equipped in each of their vertices  with root trees with  n vertices,  from each of which the edge  leads directly to the root   dn  M 2   A group of cycles of  t length,  equipped with  t an ‐vertex trees  with  n floors, and  an group of  an ‐ vertex trees with  n floors  n  2, an dt  k   M             diOti   i dTan   d  En  Ot   kEn   d T 1  Ot   kTn1    n d  En  A1    d T 1 T21   

n   d T n  Ot   kT n   a a

dOt – for M  2p , K  4l 1 , l    1 , and C  2m  1 , m    0 . Under these conditions: a) for l  2k2  K  2k 1 , k  2 , t  2M  K 1 , and d   K  1 2 (or t  2 pl1 , d  2l1 ) take place; b) for l  2k 1  K  8k  5 , k  1 , t  M 2 , and d  2 take place; c) for l  2k , k  1 , K  2r 1, r  3 (that is k  2r3 : k  2i4  2 j  1 , and l  2i3  2 j  1  K  2i1 2 j  1 1 for j  1; 2 pi 1 , i 4; p 1 ), t  M 2i2 , d  2i2 take place; dOt  O1 – for simple M , K  2 , C   ; a tree with a root, zero cycle, for М  2p , K 2l : l  , 0  l  2 p1 , C 0,1,, 2 p 1 , 3.2.

Generalized graph of states of linear congruential generator 

Analysis of possible graphs of LCG states shows that they can all be reduced to a single configuration containing a set of d cycles of the same or different length, including zero cycles, and a set of d ' precycles (trees) leading to cycles. Under these conditions

d d ' M  ti  t'j ,  (2) 

i1 j1 where ti is the length of the i th cycle;

t'j is the number of vertices in the j th tree except for the root.

The generalized LCG graph can be represented as follows: where VLCG is the set of vertices of the graph;

ALCG is the set of arcs of the graph.

In its turn,

GLCG  VLCG , ALCG  , VLCG  vk   vl'  , ALCG  ak   al'  , d where ak  is the set of arcs belonging to the cycles, k  1, 2,,  ti ; i1 d ' al'  is the set of arcs belonging to the trees, l  1, 2,, t'j . j1 According to [33], for a simple M , the expressions d '  0 , ti  t for i1,d 1 and td  1 are d 1 fair, and expression (2) takes the form: M   t  1 .

i1

We present a generalized graph of LCG states in terms of the theory of algebra of monads and the topology of monad graphs.

The analysis of typical oriented graphs of LCG states shows that no more complex patterns, except for the products of trees and cycles, are found in the graphs of monads of f : S  S representation. LCG graph is an inconnected combination of cycles equipped with tree products. Since En  T 1  O1 , n At  T21  Ot , Dt  T41  Ot , each connected component of LCG graph can be represented as d where vk  is the set of vertices belonging to the cycles, k  1, 2,,  ti ; i1 d ' vl'  is the set of vertices belonging to the trees, except for their roots, l  1, 2,, t'j ; j1 T n  Tbm  Ot  .

a

For example,

Ot  Ta0  Tb0  Ot  , and

At  Ta0  T21  Ot   T21  Tb0  Ot  , ai , ni , bi , mi , ti are parameters of connectivity components of the graph of LCG states of the i th type.

d In this case  diaini bimi ti  M .

i1 d Determining the rules for calculating the number of graph components  di , their types d and i1 values of numbers ai , ni , bi , mi , ti through LCG parameters is beyond the scope of this work and requires further research. 3.3. Method  for  generating  sequences  of  permutations  based  on  linear  congruential method 

The method for generating LCG-based PRS is as follows. 1. If necessary (for example, to increase the speed of PRS generating or meet the requirements for the spatial complexity of the algorithm that implements the proposed method), the type of graph of LCG states, as well as the conditions to be met by K , C and M LCG parameters to obtain a given type of structure are determined. Determining the type of the graph of LCG states can be performed in accordance with typical graphs presented in Table 3. M parameter determines the area of determination of pseudorandom variable. If the choice of the type of the graph of states is not made, LCG parameters are determined arbitrarily, taking into account the restrictions imposed on them. 2. If necessary (for example, for non-consecutive cycles of the graph of LCG states without precycles (trees) to increase the speed of PRS generating), the representatives of each cycle of the generator (boot vectors (BVs)) are determined and stored in memory. 3. The current LCG BV is determined by (random or deterministic) choosing from the set of stored BVs, if this set is specified, or from the set of integers in the range 0, M 1 . 4. A PRS is formed by the LCG with given parameters until the generator forms unique numbers. In the case of reappearance of any element (not necessarily equal to BV (for a graph containing continuous cycles without precycles (trees), equal to BV)) the generation of the current segment of the sequence is stopped. 5. A new current BV of LCG is determined by its (random or deterministic) choosing:  from the set of still unused BVs, if this set is specified;  from the set of integers of the range 0, M 1 except for the numbers present in the formed part of the PRS. 6. PRS is formed for a given BV until the reappearance of the element in the formed sequence (for a graph containing continuous cycles without precycles (trees), equal to the current BV). 7. Transition to item five until the shuffle of all BVs. 8. Transition to item three until the shuffle of all combinations consistently used in items three and five of BV (if they are set and stored in memory). 9. Transition to item two until the shuffle of all BV combinations (if they are set and stored in memory).

Thus, the proposed method allows performing concatenation not only of separate and disjoint cycles in LCG graph, but also of precycles (trees), if they are contained therein.

In addition, the proposed approaches can be used to form PRS based on LFSR with an arbitrary generator polynomial. This is because the use of a reducible polynomial as a generator one for LFSR leads to an increase in the number and the change in the structure of connected components in the generator graph of states.

4. Experiments and results 

The proposed approaches to constructing devices for PRS generating based on LCG are used to create software implementations of generators.

The size of the space of allowable values of LCG parameters for the above method is equal to M 2 . The comparison with the corresponding indicators of the analogues in table 1 shows that this method allows increasing the size of the space of allowable values of LCG parameters to achieve the PRS period T  M in M   M  times.

Let us study the speed of software implementation of the permutation generator based on the developed method and compare it with the speed of the generator that implements the modern FisherYates algorithm [34]. For the sake of objectivity, the generators were implemented on one platform and tested on one computer with fixed performance indicators. The results are presented in Figure 3.

Figure 3: Graphs of dependence of speed of permutation generators on  M  value 

The speed of the developed generator exceeds the speed of the permutation generator using the Fisher-Yates algorithm for M  125 , which expands the results obtained in [35].

It should be noted that PRS formed according to the proposed method is not cryptographically stable and can not be used in "pure" form in cryptographic transformations, for example, as a gamma for stream ciphers. However, the proposed approaches to PRS generating can be used to implement a multi-stage encryption procedure.

5. Conclusions 

The scientific novelty of the study is as follows. It is developed the model for generalized graph of states of linear congruential generator, which allows to carry out the classification of types of connectivity components of the graph of its states and to investigate the influence of parameters on its topology. The developed model has allowed to improve the method for PRS generating based on linear congruential method, which allows to form PRS of uniformly distributed numbers regardless of the topology of the graph of states of linear congruential generator and, as a result, to minimize the time spent on choosing its parameters and increase the size of the space of their allowable values to achieve the PRS period T  M in M   М  times.

Implementation of the algorithm for generating PRS of permutations based on LCG with any type of the graph of its states has allowed to increase the speed of the generator compared to the permutation generator based on PRNG LFIB78 using the Fisher-Yates algorithm for the permutation order M  125 : in particular, for M  20 – in 2.1 times; M  50 – 1.6 times; M  100 – 1.2 times.

6. Acknowledgements 

This research was funded by the Ministry of Education and Science of Ukraine, grant number 0120U102607.

7. References 

References

[1] D. E. Knuth , The Art of Computer Programming , Vol. 2 : Seminumerical Algorithms , 3rd ed., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1997 .

[2] F. James , L. Moneta , Review of high-quality random number generators , Computing and Software for Big Science 4 ( 1 ) ( 2020 ). doi: 10.1007/s41781-019-0034-3.

[3] L. Crocetti , S. Di Matteo , P. Nannipieri , L. Fanucci , S. Saponara , Design and test of an integrated random number generator with all-digital entropy source , Entropy 24 ( 2 ) ( 2022 ). doi: 10 .3390/e24020139.

[4] X. Tong , X. Chen , S. Xu, Advances in superlattice cryptography research, [超晶格密码的研究进展] Kexue Tongbao/Chinese Science Bulletin 65 ( 2-3 ) ( 2020 ) 108 - 116 . doi 10.1360/TB-2019-0291.

[5] S. Sysoienko , I. Myronets , V. Babenko , Practical implementation effectiveness of the speed increasing method of group matrix cryptographic transformation , in: CEUR Workshop Proceedings , volume 2353 , 2019 , pp. 402 - 412 .

[6] S. Gnatyuk , V. Kinzeryavyy , K. Kyrychenko , Kh. Yubuzova, M. Aleksander , R. Odarchenko , Secure hash function constructing for future communication systems and networks , Advances in Intelligent Systems and Computing 902 ( 2020 ) 561 - 569 .

[7] M. Alawad , M. Lin , Survey of stochastic-based computation paradigms , IEEE Transactions on Emerging Topics in Computing 7 ( 1 ) ( 2019 ) 98 - 114 . doi 10.1109/TETC. 2016 . 2598726 .

[8] S. Bandyopadhyay , R. Bhattacharya , Discrete and Continuous Simulation: Theory and Practice , CRC Press, 2014 . doi: 10 .1201/b17127.

[9] P. A. A. Resende , A. C. Drummond , A survey of random forest based methods for intrusion detection systems , ACM Computing Surveys 51 ( 3 ) ( 2018 ). doi: 10 .1145/3178582.

[10] J. S. Al-Azzeh , B. Ayyoub , E. Faure , V. Shvydkyi , O. Kharin , A. Lavdanskyi , Telecommunication systems with multiple access based on data factorial coding , International Journal on Communications Antenna and Propagation 10 ( 2 ) ( 2020 ) 102 - 113 . doi: 10 .15866/irecap.v10i2. 17216 .

[11] E. Faure , A. Shcherba , Y. Vasiliu , A. Fesenko , Cryptographic key exchange method for data factorial coding , in: CEUR Workshop Proceedings , volume 2654 , 2020 , pp. 643 - 653 .

[12] E. Faure , A. Shcherba , B. Stupka , Permutation-based frame synchronisation method for short packet communication systems , in: Proceedings of the 11th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications , IDAACS 2021 , volume 2 , 2021 , pp. 1073 - 1077 . doi: 10 .1109/IDAACS53288. 2021 . 9660996 .

[13] D. H. Lehmer , Mathematical methods in large-scale computing units , in: Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery , Cambridge, Mass., 1949 , pp. 141 - 146 .

[14] W. Freiberger , U. Grenander , A Short Course in Computational Probability and Statistics, Springer, New York, 1971 .

[15] M. Greenberger , An a priori determination of serial correlation in computer generated random numbers , Mathematics of Computation 15 ( 76 ) ( 1961 ) 383 .