Four Cellular Automata Algorithms for Matrix Permutation
Numerical calculation uses to describe the operation of matrix permutation algorithms based on cyclic shifts of rows and columns. This choice of discrete transformation algorithms justified by the convenience of the cellular automaton (CA) formulation, which is used. Obtained Empirical formulas for...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
MGTU im. N.È. Baumana
2020-12-01
|
| Series: | Matematika i Matematičeskoe Modelirovanie |
| Subjects: | |
| Online Access: | https://www.mathmelpub.ru/jour/article/view/223 |
| _version_ | 1818268516521869312 |
|---|---|
| author | I. V. Matyushkin P. D. Rubis |
| author_facet | I. V. Matyushkin P. D. Rubis |
| author_sort | I. V. Matyushkin |
| collection | DOAJ |
| description | Numerical calculation uses to describe the operation of matrix permutation algorithms based on cyclic shifts of rows and columns. This choice of discrete transformation algorithms justified by the convenience of the cellular automaton (CA) formulation, which is used. Obtained Empirical formulas for the permutation period and for the last algorithm, which period formula is recurrent. For a base scheme period has the asymptotics: for a matrix with pairwise different elements. Despite the complexity of the scheme, the other two modifications only give a polynomial growth of period, no higher than 3. Fourth scheme has a non-trivial period dependence, but no higher than the exponential. In some cases algorithms make special permutations: rotate, reflect, and rearrange blocks for the matrix . These formulas are closely related to individual cells paths. And paths connected with the influence of the boundaries that gives branching the matrix order by subtraction class modulo 3,4 or 12. Visualizations of these paths make in the extended CA-field. Two "mixing metrics" analyze as a parameter of CA dynamics on matrix permutations (compared to the initial). For all schemes and most branches, the behavior of these metrics shows in graphs and histograms (conditional density distribution) showing how often the permutation period occurs with the specified interval of metrics. The practical aim of this work is in the field of pseudorandom number generation and cryptography. |
| first_indexed | 2024-12-12T20:39:44Z |
| format | Article |
| id | doaj.art-fcb952a9636e4f0a92b04e9cb43467e6 |
| institution | Directory Open Access Journal |
| issn | 2412-5911 |
| language | Russian |
| last_indexed | 2024-12-12T20:39:44Z |
| publishDate | 2020-12-01 |
| publisher | MGTU im. N.È. Baumana |
| record_format | Article |
| series | Matematika i Matematičeskoe Modelirovanie |
| spelling | doaj.art-fcb952a9636e4f0a92b04e9cb43467e62022-12-22T00:12:48ZrusMGTU im. N.È. BaumanaMatematika i Matematičeskoe Modelirovanie2412-59112020-12-010415110.24108/mathm.0420.0000223149Four Cellular Automata Algorithms for Matrix PermutationI. V. Matyushkin0P. D. Rubis1JSC Molecular Electronics Research Institute, Moscow, Zelenograd; National Research University of Electronic Technology, Moscow, ZelenogradNational Research University of Electronic Technology, Moscow, ZelenogradNumerical calculation uses to describe the operation of matrix permutation algorithms based on cyclic shifts of rows and columns. This choice of discrete transformation algorithms justified by the convenience of the cellular automaton (CA) formulation, which is used. Obtained Empirical formulas for the permutation period and for the last algorithm, which period formula is recurrent. For a base scheme period has the asymptotics: for a matrix with pairwise different elements. Despite the complexity of the scheme, the other two modifications only give a polynomial growth of period, no higher than 3. Fourth scheme has a non-trivial period dependence, but no higher than the exponential. In some cases algorithms make special permutations: rotate, reflect, and rearrange blocks for the matrix . These formulas are closely related to individual cells paths. And paths connected with the influence of the boundaries that gives branching the matrix order by subtraction class modulo 3,4 or 12. Visualizations of these paths make in the extended CA-field. Two "mixing metrics" analyze as a parameter of CA dynamics on matrix permutations (compared to the initial). For all schemes and most branches, the behavior of these metrics shows in graphs and histograms (conditional density distribution) showing how often the permutation period occurs with the specified interval of metrics. The practical aim of this work is in the field of pseudorandom number generation and cryptography.https://www.mathmelpub.ru/jour/article/view/223cellular automatapermutationrandom numberscryptographymetric |
| spellingShingle | I. V. Matyushkin P. D. Rubis Four Cellular Automata Algorithms for Matrix Permutation Matematika i Matematičeskoe Modelirovanie cellular automata permutation random numbers cryptography metric |
| title | Four Cellular Automata Algorithms for Matrix Permutation |
| title_full | Four Cellular Automata Algorithms for Matrix Permutation |
| title_fullStr | Four Cellular Automata Algorithms for Matrix Permutation |
| title_full_unstemmed | Four Cellular Automata Algorithms for Matrix Permutation |
| title_short | Four Cellular Automata Algorithms for Matrix Permutation |
| title_sort | four cellular automata algorithms for matrix permutation |
| topic | cellular automata permutation random numbers cryptography metric |
| url | https://www.mathmelpub.ru/jour/article/view/223 |
| work_keys_str_mv | AT ivmatyushkin fourcellularautomataalgorithmsformatrixpermutation AT pdrubis fourcellularautomataalgorithmsformatrixpermutation |