Preview

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

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

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

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

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

Аннотация

С помощью численного расчета описывается работа алгоритмов пермутаций матриц, основанных на циклических сдвигах строк и столбцов. Такой выбор алгоритмов дискретного преобразования обоснован удобством клеточно-автоматных формулировок, которые и приводятся. Получены эмпирические формулы для периода пермутаций; для последнего алгоритма формула периода носит рекуррентный характер. Для базовой и наиболее простой схемы период N(n) имеет асимптотику exp(2n)/n для матрицы nxn с попарно различными элементами. Несмотря на усложнение схемы алгоритма, две другие модификации дают лишь полиномиальный рост степени не выше 3. Четвертая схема имеет нетривиальную зависимость периода, но не выше экспоненциальной. В ряде случаев алгоритмы порождают особые пермутации: поворот, отражение и перестановку блоков для матрицы 2kx2k. Эти формулы тесно связаны с индивидуальными траекториями элементов, а они – с влиянием границ, что дает ветвление порядка матрицы по классу вычета по модулю 3,4 или 12. Визуализации этих траекторий приводятся в расширенном поле КА. В качестве параметра динамики КА анализируются две «метрики перемешанности» на пермутациях матрицы (по сравнению с начальной). Для всех схем и большинства ветвей поведение этих метрик представлено на графиках и гистограммах (условно: плотности распределения), показывающих, как часто встречаются по периоду пермутации с заданным интервалом значений метрик. Практическое значение работы состоит в оценке применения КА в областях генерации псевдослучайных чисел и криптографии.

Об авторах

И. В. Матюшкин
Национальный исследовательский университет Московский институт электронной техники, Москва, Зеленоград; НИИ Молекулярной Электроники, Москва, Зеленоград
Россия
Матюшкин Игорь Валерьевич


П. Д. Рубис
Национальный исследовательский университет Московский институт электронной техники, Москва, Зеленоград; НИИ Молекулярной Электроники, Москва, Зеленоград
Россия
Рубис Павел Дмитриевич


Список литературы

1. Wolfram S. Random Sequence Generation by Cellular Automata // Advances in Applied Mathematics, 1986, vol. 7, Pp. 429 – 432.

2. Сухинин Б. М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Машиностроение и компьютерные технологии. 2010. №9. Режим доступа: https://cyberleninka.ru/article/n/razrabotka-generatorov-psevdosluchaynyh-dvoichnyh-posledovatelnostey-na-osnove-kletochnyh-avtomatov (дата обращения: 25.08.2020).

3. Ярмолик В.Н., Мурашко И. А. Реализация генератора псевдослучайной последовательности на клеточных автоматах // Автоматика и вычислительная техника. 1993. №3. С. 9-13.

4. Bar dell P. Analysis of cellular automata used as pseudorandom pattern generators // Proceeings., International Test Conference. 1990. Pp. 762-768.

5. 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.

6. Мухамеджанов Д.Д., Левина А.Б. Генератор псевдослучайных чисел на основе клеточных автоматов // Научно-технический вестник информационных технологий, механики и оптики. 2018. №5. С 894–900. DOI: 10.17586/2226-1494-2018-18-5-894-900

7. S. Bilan, M. Bilan, S. Bilan, Novel pseudo-random sequence of numbers generator based cellular automata. // Information Technology and Security. – 2015. – Vol. 3, Iss. 1 (4). – Pp. 38–50. DOI: doi.org/10.20535/2411-1031.2015.3.1.57710

8. Bruno Martin, Patrick Solé. Pseudo-random Sequences Generated by Cellular Automata. International Conference on Relations, Orders and Graphs: Interactions with Computer Science, May 2008, Mahdia, Tunisia, Pp. 401-410.

9. Agrawal V, Bushnell M. Essentials of Electronic Testing for Digital, Memory, and Mixed-Signal VLSI Circuits. Springer, 2000. Pp. 712.

10. Hortensius P.D. Parallel random number generation for VLSI systems using cellular automata // IEEE Transactions on Computers. 1989. Vol. 28 (10). Pp. 1466-1473.

11. Fog A. Pseudo-Random Number Generators for Vector Processors and Multicore Processors. // Journal of modern applied statistical methods. 2015. №14(1) Pp 308 - 334.

12. Ключарёв П.Г. Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах. // Математика и математическое моделирование. 2017. №3. С. 77-90. DOI: 10.24108/mathm.0317.0000076.

13. Конахович Г.Ф. , Пузыренко А.Ю. Компьютерная стеганография Теория и практика. К "МК-Пресс" 2006. Гл. 5. С. 92-97.

14. Chen Y. L., Lambooij E., Mennink B. How to Build Pseudorandom Functions From Public Random Permutations Cryptology. Cryptology ePrint Archive. Available at https://eprint.iacr.org/2019/554.pdf , accessed 09.07.2020.

15. Trevisan L. U.C. Berkeley — CS276: Cryptography: Notes for Lecture 15. Available at https://people.eecs.berkeley.edu/~luca/cs276/lecture15.pdf , accessed 09.07.2020.

16. Rubio, C. F., L. Encinas, S. H. White, Á. Rey and G. Sánchez. The Use of Linear Hybrid Cellular Automata as Pseudo Random Bit Generators in Cryptography. // Neural Parallel & Scientific Comp. 2004. №12. Pp 175-192.

17. Жуков Д. А. О порядке одной перестановки на элементах квадратной матрицы // Десятая международная научно-технической конференция «Безопасные информационные технологии»: труды. М.: Москва, Изд-во Московский государственный технический университет имени Н.Э. Баумана (национальный исследовательский университет) (Москва), 2019. С. 143-145.

18. 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. №11. Pp. 50–61.

19. Матюшкин И.В., Кожевников В.С Клеточно-автоматные алгоритмы пермутации матриц // ТРУДЫ МФТИ. 2019. Том 11, № 1. С.39-52.

20. Матюшкин И.В., Кожевников В.С. Клеточно-автоматный алгоритм пермутации мат-риц // Математика и математическое моделирование. 2019. №3. С. 1-24.

21. Деза Е.И., Деза М.М. Энциклопедический словарь расстояний: пер. с англ. М.: Наука, 2008. 444 с. [Deza E., Deza M.M. Dictionary of distances. Amst.: Elsevier, 2006. 391 p.].


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


Матюшкин И.В., Рубис П.Д. Четыре клеточно-автоматных алгоритма пермутаций матриц. Математика и математическое моделирование. 2020;(4):1-51. https://doi.org/10.24108/mathm.0420.0000223

For citation:


Matyushkin I.V., Rubis P.D. Four Cellular Automata Algorithms for Matrix Permutation. Mathematics and Mathematical Modeling. 2020;(4):1-51. (In Russ.) https://doi.org/10.24108/mathm.0420.0000223

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


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


ISSN 2412-5911 (Online)