Математика и математическое моделирование. 2019; : 1-24
Клеточно-автоматный алгоритм пермутации матриц
Аннотация
В статье описывается алгоритм, осуществляющий перестановку элементов матрицы посредством циклических сдвигов строк и столбцов. Дано формальное описание клеточного автомата (КА), реализующего данный алгоритм. Для этого используется квадратная решётка размера n×n с замкнутыми границами и окрестность клетки типа фон Неймана.
В результате вычислительного эксперимента для начальных порядков матрицы n установлено, что через достаточно большое число шагов алгоритм переводит матрицу в исходную, т.е. имеет период N. Для нечётных порядков матрицы рост N как функции n оказывается быстрее экспоненциального.
Проведён анализ движения отдельных элементов матрицы. Показано, что они перемещаются по аналогии с бильярдными шарами. Элемент двигается под углом 45° к границам матрицы и меняет направление при достижении границы. Найдена явная зависимость периода движения элемента от его начального положения в матрице. На основе этой зависимости доказано, что глобальный период N равен наименьшему общему кратному всех нечетных чисел, меньших 2n, т.е. N=НОК(3,5,…,2n-1).
Динамика пермутаций проанализирована с помощью введенных авторами двух «метрик», отражающих степень перемешанности. Одна из метрик вводится специально для матрицы, другая — для линейного массива и зависит от способа преобразования матрицы в одномерный массив. Поиском перестановок с экстремальными значениями метрик установлено, что в результате пермутаций матрицы чётных порядков подвергаются блочной перестановке. В случае же нечётного порядка матрица претерпевает поворот на ±90° и на 180° (отражение относительно центра). При этом направление вращение зависит от порядка n. Например, при n=5 вращение происходит против часовой стрелки, а при n=7 — по часовой стрелке.
Алгоритм может быть использован для генерации псевдослучайных чисел, в пользу чего косвенно говорит величина его периода. Период может быть существенно увеличен небольшим усложнением алгоритма, например, введением различных длин для циклов смены направления столбцов и строк. Останавливая алгоритм в случайный момент времени, текущую перестановку матрицы можно рассматривать как массив случайных чисел или же преобразовать её каким-либо способом в одно случайное число.
Список литературы
1. Матюшкин И.В. Алгоритмы параллельных вычислений в формализации клеточных автоматов: сортировка строк и умножение чисел по схеме Атрубина // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2016. № 4. С. 77–81.
2. Матюшкин И.В., Жемерикин А.В., Заплетина М.А. Клеточно-автоматные алгоритмы сортировки строк и умножения целых чисел по схеме Атрубина // Изв. высш. учеб. заведений. Электроника. 2016. Т. 21. № 6. С. 557–565.
3. Матюшкин И.В., Заплетина М.А. Отражение и транспонирование данных в матрице клеточно-автоматного вычислителя // Изв. высш. учеб. заведений. Электроника. 2019. Т. 24. № 1. С. 51–63. DOI: 10.24151/1561-5405-2019-24-1-51-63
4. Ji Won Yoon, Hyoungshick Kim. An image encryption scheme with a pseudorandom permutation based on chaotic maps // Communications in Nonlinear Science and Numerical Simulation. 2010. Vol. 15. No. 12. Pp. 3998–4006. DOI: 10.1016/j.cnsns.2010.01.041
5. Weichuang Guo, Junqin Zhao, Ruisong Ye. A chaos-based pseudorandom permutation and bilateral diffusion scheme for image encryption // Intern. J. of Image, Graphics and Signal Processing. 2014. Vol. 6. No. 11. Pp. 50–61. DOI: 10.5815/ijigsp.2014.11.07
6. Kaur M., Kumar V. Efficient image encryption method based on improved Lorenz chaotic system // Electronics Letters. 2018. Vol. 54. No. 9. Pp. 562–564. DOI: 10.1049/el.2017.4426
7. Fridrich J. Symmetric ciphers based on two-dimensional chaotic maps // Intern. J. of Bifurcation and Chaos in Applied Sciences and Engineering. 1998. Vol. 8. No. 6. Pp. 1259–1284. DOI: 10.1142/S021812749800098X
8. Vinod Patidar, Pareek N.K., Purohit G., Sud K.K. A robust and secure chaotic standard map based pseudorandom permutation-substitution scheme for image encryption // Optics Communications. 2011. Vol. 284. No. 19. Pp. 4331–4339. DOI: 10.1016/j.optcom.2011.05.028
9. Girau B., Vlassopoulos N. Evolution of 2-dimensional cellular automata as pseudo-random number generators // Cellular automata: 10th Intern. conf. on cellular automata for research and industry: ACRI 2012 (Santorini island, Greece, Sept. 24-27, 2012): Proc. B.; Hdbl.: Springer, 2012. Pp. 611-622. DOI: 10.1007/978-3-642-33350-7_63
10. Souyah A., Faraoun K.M. An image encryption scheme combining chaos-memory cellular automata and weighted histogram // Nonlinear Dynamics. 2016. Vol. 86. No. 1. Pp. 639–653. DOI: 10.1007/s11071-016-2912-0
11. Ключарёв П.Г. Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах // Математика и математическое моделирование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2017. № 3. С. 77–90. DOI: 10.24108/mathm.0317.0000076
12. Деза Е.И., Деза М.М. Энциклопедический словарь расстояний: пер. с англ. М.: Наука, 2008. 444 с. [Deza E., Deza M.M. Dictionary of distances. Amst.: Elsevier, 2006. 391 p.].
Mathematics and Mathematical Modeling. 2019; : 1-24
A Cellular Automata Algorithm for Matrix Permutations
Abstract
The article describes an algorithm to provide permutation of matrix elements through cyclic shifts of rows and columns and gives a formal description of a cellular automaton (CA) that implements this algorithm. For this, a square n × n lattice with closed boundaries and a neighbourhood of a von Neumann type cell are used.
As a result of a computational experiment for the initial orders of the matrix n, it was found that after a sufficiently large number of steps, the algorithm transfers the matrix to the original one, i.e. has period N. For odd orders of the matrix, the growth of N as a function of n is faster than exponential.
A movement of the individual elements of the matrix has been analysed to show that they move in a manner similar to billiard balls. The element moves to the matrix boundaries at an angle of 45 ° and changes direction when it reaches the bound. A defined explicit dependence of the element movement period on its initial position in the matrix allows us to prove that the global period N is equal to the least common multiple of all the odd numbers being less than 2n, i.e. N = LCM(3,5, ..., 2n-1).
To analyse the permutation dynamics, two authors-introduced “metrics” that reflect a degree of randomizing were used. One of the metrics is introduced specifically for the matrix, the other for the linear array and depends on how the matrix is transformed into a one-dimensional array. By searching for permutations with extreme metric values, it was found that as a result of permutations, even-order matrices undergo block permutation. In the case of an odd order, the matrix undergoes a rotation of ± 90 ° and 180 ° (reflection relative to the centre). Moreover, the direction of rotation depends on the order n. For example, for n = 5, counter-clockwise rotation occurs, and for n = 7, it is clockwise.
The algorithm can be used to generate pseudorandom numbers, and a value of its period indirectly argues for it. The period can be significantly increased through a slight complication of the algorithm, for example, by introducing different lengths for cycles of changing a direction of columns and rows. Stopping the algorithm at random time, one can consider the current permutation of the matrix as an array of random numbers or somehow transform it into one random number.
References
1. Matyushkin I.V. Algoritmy parallel'nykh vychislenii v formalizatsii kletochnykh avtomatov: sortirovka strok i umnozhenie chisel po skheme Atrubina // Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh sistem (MES). 2016. № 4. S. 77–81.
2. Matyushkin I.V., Zhemerikin A.V., Zapletina M.A. Kletochno-avtomatnye algoritmy sortirovki strok i umnozheniya tselykh chisel po skheme Atrubina // Izv. vyssh. ucheb. zavedenii. Elektronika. 2016. T. 21. № 6. S. 557–565.
3. Matyushkin I.V., Zapletina M.A. Otrazhenie i transponirovanie dannykh v matritse kletochno-avtomatnogo vychislitelya // Izv. vyssh. ucheb. zavedenii. Elektronika. 2019. T. 24. № 1. S. 51–63. DOI: 10.24151/1561-5405-2019-24-1-51-63
4. Ji Won Yoon, Hyoungshick Kim. An image encryption scheme with a pseudorandom permutation based on chaotic maps // Communications in Nonlinear Science and Numerical Simulation. 2010. Vol. 15. No. 12. Pp. 3998–4006. DOI: 10.1016/j.cnsns.2010.01.041
5. Weichuang Guo, Junqin Zhao, Ruisong Ye. A chaos-based pseudorandom permutation and bilateral diffusion scheme for image encryption // Intern. J. of Image, Graphics and Signal Processing. 2014. Vol. 6. No. 11. Pp. 50–61. DOI: 10.5815/ijigsp.2014.11.07
6. Kaur M., Kumar V. Efficient image encryption method based on improved Lorenz chaotic system // Electronics Letters. 2018. Vol. 54. No. 9. Pp. 562–564. DOI: 10.1049/el.2017.4426
7. Fridrich J. Symmetric ciphers based on two-dimensional chaotic maps // Intern. J. of Bifurcation and Chaos in Applied Sciences and Engineering. 1998. Vol. 8. No. 6. Pp. 1259–1284. DOI: 10.1142/S021812749800098X
8. Vinod Patidar, Pareek N.K., Purohit G., Sud K.K. A robust and secure chaotic standard map based pseudorandom permutation-substitution scheme for image encryption // Optics Communications. 2011. Vol. 284. No. 19. Pp. 4331–4339. DOI: 10.1016/j.optcom.2011.05.028
9. Girau B., Vlassopoulos N. Evolution of 2-dimensional cellular automata as pseudo-random number generators // Cellular automata: 10th Intern. conf. on cellular automata for research and industry: ACRI 2012 (Santorini island, Greece, Sept. 24-27, 2012): Proc. B.; Hdbl.: Springer, 2012. Pp. 611-622. DOI: 10.1007/978-3-642-33350-7_63
10. Souyah A., Faraoun K.M. An image encryption scheme combining chaos-memory cellular automata and weighted histogram // Nonlinear Dynamics. 2016. Vol. 86. No. 1. Pp. 639–653. DOI: 10.1007/s11071-016-2912-0
11. Klyucharev P.G. Postroenie sluchainykh grafov, prednaznachennykh dlya primeneniya v kriptograficheskikh algoritmakh, osnovannykh na obobshchennykh kletochnykh avtomatakh // Matematika i matematicheskoe modelirovanie. MGTU im. N.E. Baumana. Elektron. zhurn. 2017. № 3. S. 77–90. DOI: 10.24108/mathm.0317.0000076
12. Deza E.I., Deza M.M. Entsiklopedicheskii slovar' rasstoyanii: per. s angl. M.: Nauka, 2008. 444 s. [Deza E., Deza M.M. Dictionary of distances. Amst.: Elsevier, 2006. 391 p.].
