Preview

Математика и математическое моделирование

Расширенный поиск

Клеточно-автоматный алгоритм пермутации матриц

https://doi.org/10.24108/mathm.0319.0000181

Полный текст:

Аннотация

В статье описывается алгоритм, осуществляющий перестановку элементов матрицы посредством циклических сдвигов строк и столбцов. Дано формальное описание клеточного автомата (КА), реализующего данный алгоритм. Для этого используется квадратная решётка размера 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.].


Для цитирования:


Матюшкин И.В., Кожевников В.С. Клеточно-автоматный алгоритм пермутации матриц. Математика и математическое моделирование. 2019;(3):1-24. https://doi.org/10.24108/mathm.0319.0000181

For citation:


Matyushkin I.V., Kozhevnikov V.S. A Cellular Automata Algorithm for Matrix Permutations. Mathematics and Mathematical Modeling. 2019;(3):1-24. (In Russ.) https://doi.org/10.24108/mathm.0319.0000181

Просмотров: 33


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)