Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Генератор псевдослучайных чисел на основе клеточных автоматов и игры "Жизнь"

С.А. Мирзоян

Аннотация

Генераторы псевдослучайных чисел имеют широкое применение в сферах науки:математика, криптография, нейронные сети, моделирование, медицина. Предложенметод генерациислучайныхчиселна основе клеточного автомата, правила поведения в которого определяются игрой «Жизнь». Разработанный алгоритм протестирован в ряде тестов, произведен сравнительный тест со линейно-конгруэнтным методом генерации случайных чисел, а также с другим генератором случайных чисел, также основанном также на технологии клеточных автоматов. Во всех тестах алгоритм показал отличные результаты, а простота реализации и особенности технологии клеточных автоматов скрывают большой потенциал в развитии данного метода.

Ключевыеслова генератор псевдослучайное число игра жизнь

Генератор псевдослучайных чисел, клеточный автомат, клетка, последовательность

PSEUDORANDOM NUMBER GENERATOR BASED ON CELLULAR AUTOMATA AND THE GAME " LIFE»

S. Mirzoyan

V. Gradov

Abstract

Pseudorandom number generator, cellular automaton, cell, sequence

Введение

Генераторы псевдослучайных чисел (ГПСЧ) являют собой технологию создания последовательностей случайных чисел и широко применяются в различных областях, например в таких, как криптография, моделирование, медицина, нейронные сети, тестирование. Ввиду этого создание качественныхГПСЧ является актуальной задачей современной науки и требует глубокого и качественного изучения.

Достигнуты значительныеуспехивнаправлениилинейно-конгруэнтныхгенераторов[8,9] ивихревых алгоритмическихгенераторов[10 -13]. Тем не менее остаются открытыми вопросыполнотынаборовэлементов и повторяемостиэлементов полученной последовательности.

Основные понятия теории клеточных автоматов

Клеточные автоматы - это дискретные динамические системы, поведение которых полностью определяется в терминах локальных зависимостей, в значительной в значительной степени так же обстоит дело для большого класса непрерывных динамических систем, определенных уравнениями в частных производных. [2]

Клеточный автомат можно формально описать как четверку

, (1)

где - множество мерных векторов, = - множество состояний одной ячейки в , - окрестность или шаблон соседства (упорядоченное множество различных -мерных векторов из , - локальная функция переноса.[3-4]

Особенность клеточного автомата заключается в том, что на очередном шаге состояние каждой клетки зависит от состояния клеток вокруг нее - ее окрестности. Обычно различают два вида окрестностей: окрестность Мура и окрестность фон Неймана [5] (рисунок 1).

Рисунок 1. Окрестности фон Неймана (слева) и Мура (справа)

В основе представленного алгоритма лежит игра «Жизнь». «Жизнь» -- это клеточный автомат, в котором соблюдается ряд определенных правил поведения системы. В результате выполнения классических условий игры через некоторое количество ходов по выбору методики генерирования получается последовательность псевдослучайных чисел из нулей и единиц. В данной же реализации была произведена модификация условий, благодаря которым последовательность состоит из значений множества А = {0; 1; 2}.

Игра «Жизнь»

«Жизнь» -- это клеточный автомат,придуманный математиком Джоном ХортономКонвеем в 1970 году. Создавая игру, он вдохновлялся проблемой, предложенной Джоном фон Нейманом - самовоспроизводящаяся машина. Конвей пытался упросить решение фон Неймана и в ходе исследований смог определить правила игры.[8]

Правила игры таковы:

1. Зарождение: Каждая пустая клетка, примыкающая ровно к трем соседям ни больше, ни меньше, - является клеткой рождения. На следующем ходу на него ставится счетчик.

2. Выживание: Каждый счетчик с двумя или тремя соседними счетчиками выживает до следующего поколения.

3. Смерть: Каждый счетчик с четырьмя и более соседями умирает (удаляется) от перенаселения. Каждый счетчик с одним соседом или без него умирает от изоляции.

Метод генерации псевдослучайных чисел

Суть работы представленного метода генерации псевдослучайных чисел заключается в следующем: предложить правила для игры «Жизнь», использовать достоинства клеточных автоматов, и обосновать их преимущества в сравнении с классическими методами генерации (для примера возьмем линейный конгруэнтный метод).

Сетка КА

В качестве математической модели рассматривается матрица, каждая ячейка которой может находиться в трех состояниях: мертвая (0), живая (1) и зомби (2). Состояния ячеек изменяются согласно правилам игры «Жизнь». Использование троичного подхода, в отличие от более привычного двоичного, позволяет внести заметную хаотичность в рисунки игры. В результате шагов в алгоритме будет получено троичное число, которое можно сформировать из сетки, из ее части или каким-либо особым способом, который выберет пользователь.

Начальная конфигурация

Для успешной работы алгоритма требуется правильный выбор начальных условий. В список начальных условий входят:

* Начальное расположение живых и зомби клеток на сетке

* Правила поведения для живых и зомби клеток

* Количество шагов

В качестве начального расположения клеток на сетке выбран следующий принцип: если клетка находится на четной позиции в строке, то она находится в состоянии «живая» (1), иначе мертвая (0)

Модифицированные правила игры «Жизнь» выбраны следующие:

• в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;

• если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; впротивном случае клетка умирает;

• в зомби клетке, рядом с которой ровно шесть живых или зомби клеток, зарождается зомби;

• если у зомби клетки есть две или четыре живые или зомби соседки, то эта клетка остается зомби клеткой; иначе клетка умирает.

Каждая смена состояний всех клеток клеточного автомата называется поколением. Несмотря на заданные очевидным способом начальные позиции, спустя некоторое количество поколений можно наблюдать заметную хаотичность изображения. Поэтому, прежде чем получить результат, игре требуется пройти несколько поколений. Для предложенных начальной конфигурации и правил поведения достаточно 12 поколений (рисунок 2).

Рисунок 2. Жизнь в первом поколении (сверху) и в последнем (снизу).

Тестирование

Для оценки качества разработанного метода генерации псевдослучайных чисел был выбран ряд критериев, входящих в набор NIST-тестов. Тесты NIST предназначены для оценки случайности последовательностей, тем самым позволяют оценить, насколько хорошо или насколько плохо работает тот или иной генератор случайных чисел или псевдослучайных чисел и работает ли он вообще.

Ниже приведены результаты тестирования генерации псевдослучайных чисел, а также ее сравнение с другими генераторами.

Таблица 1. Результаты прохождения тестов

Для сравнительного анализа были выбраны два генератора псевдослучайных чисел. Первый - это линейный конгруэнтный генератор, пожалуй, самый популярный из ГПСЧ. Второй - это генератор, основанный также на технологии клеточных автоматов, предложенный Д. Д. Мухамеджановым и А. Б. Левиной из университета ИТМО. [3].

Таблица 2. Сравнение показателей теста с линейно конгруэнтным методом и другим методом с использованием клеточных автоматов

Исходя из данных таблицы можно заметить, что предложенный генератор не только не уступает классическому методу генерации псевдослучайных чисел (линейно-конгруэнтный метод), но и превосходит его. Также можно наблюдать, что и второй генератор, также основанный на технологии клеточного автомата, превосходит классический метод генерации псевдослучайных чисел.

Вывод

Можно заключить, что генератор действительно работает, успешно, выдает случайные последовательности и, помимо прочего, не только не уступает классическому методу генерации псевдослучайных чисел (линейно-конгруэнтный метод), но и превосходит его. Также можно наблюдать, что и второй генератор, также основанный на технологии клеточного автомата, превосходит классический метод генерации псевдослучайных чисел.

Применение ГПСЧ на практике

Как уже говорилось ранее, генератор псевдослучайных чисел применяется в различных сферах деятельности. В данной статье будет рассматриваться создание открытых ключей для шифрования. В качестве алгоритма шифрования выбран алгоритм AES128.

Расширенный стандарт шифрования (AES) - это симметричный блочный шифр, который может шифровать и расшифровывать информацию. Шифрование преобразует данные в шифротекст; расшифровка шифротекста преобразует данные обратно в исходную форму, называемую открытым текстом.

Алгоритм AES способен использовать криптографические ключи размером 128, 192 и 256 бит для шифрования и дешифрования данных в блоках по 128 бит [7].

Для создания ключа, необходимо результат работы генератора перевести в символьное представление.Написан модуль, переводящий бинарную последовательность в символы в кодировке UTF-8 (8 бит на символ). Далее полученный набор символов применяется в качестве открытого ключа для шифрования. Ниже приведены изображения, демонстрирующие вышеизложенный процесс (рисунки 3-5). Тот же ключ используется при расшифровке сообщения. При этом, в случае утери данного ключа, его можно восстановить, зная начальную конфигурацию генератора. (рисунок 6)

Рисунок 3. Оригинальный текст.

Рисунок 4. Получение ключа. В силу особенностей кодировки некоторые символы не имеют визуального представления

Рисунок 5. Зашифрованный текст.

Рисунок 6. Расшифрованный текст.

В результате расшифровки зашифрованного текста было сохранено 100% от исходного текста, что говорит об успешном применении данного метода генерации к прикладным задачам, в частности к задачам шифрования.

Заключение

В данной работе был предложен способ генерации случайных чисел на основе клеточных автоматов и игры «Жизнь». Приведены результаты тестов, а также сравнительный анализ с другими генераторами. В результате проведенных тестов предложенный ГПСЧ не только показал отличные результаты, но также вследствие сравнительного анализа позволил наблюдать интересный факт: ГПСЧ на основе клеточных автоматов дает результат лучше, чем классический линейно-конгруэнтный - один из самых популярных. Это говорит о том, что такой способ генерации случайных последовательностей скрывает за собой большой потенциал в развитии технологий создания качественных ГПСЧ. Ведь помимо очевидных преимуществ в полученном результате, технология клеточных автоматов позволяет применять многопоточность и параллельное программирование, тем самым значительно увеличивая скорость работы генератора, что особенно важно при работе с суперкомпьютерами.

ЛИТЕРАТУРА

1. Дональд Кнут. Искусство программирования, том 2. Получисленныеалгоритмы = The Art of Computer Programming, vol.2. SeminumericalAlgorithms.-- 3-е изд. -- М.: «Вильямс», 2007. -- стр 87.

2. Т. Тоффоли, Н. Марголус, Машины клеточных автоматов// Мир 1991, стр. 8.

3. Д.Д. Мухамеджанов, А.Б. Левина, Генератор псевдослучайных чисел на основе клеточных автоматов, Научно-технический вестник информационных технологий, механики и оптики, 2018, том 18, № 5, стр. 3.

4. Наумов Л.А., Шалыто А.А. Клеточные автоматы. Реализация и эксперименты // Мир ПК. 2003. № 8. стр. 64-71.

5. Aspray W. John von Neumann and the Origins of Modern Computing. MIT Press, 1990, стр. 376

6. Слеповичев И.И., ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, май 21, 2017.

7. Martin Gardner, The fantastic combinations of John Conway's new solitaire game "life", October 1970

8. Andrew Adamatzky, Game of Life Cellular Automata, 2010

References

1. Дональд Кнут. Искусство программирования, том 2. Получисленныеалгоритмы = The Art of Computer Programming, vol.2. SeminumericalAlgorithms.-- 3-е изд. -- М.: «Вильямс», 2007. -- стр 87.

2. Т. Тоффоли, Н. Марголус, Машины клеточных автоматов// Мир 1991, стр. 8.

3. Д.Д. Мухамеджанов, А.Б. Левина, Генератор псевдослучайных чисел на основе клеточных автоматов, Научно-технический вестник информационных технологий, механики и оптики, 2018, том 18, № 5, стр. 3.

4. Наумов Л.А., Шалыто А.А. Клеточные автоматы. Реализация и эксперименты // Мир ПК. 2003. № 8. стр. 64-71.

5. Aspray W. John von Neumann and the Origins of Modern Computing. MIT Press, 1990, стр. 376

6. Слеповичев И.И., ГЕНЕРАТОРЫ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ, май 21, 2017.

7. Federal Information Processing Standards Publications, ADVANCED ENCRYPTION STANDARD, November 26, 2001.

8. Andrew Adamatzky, Game of Life Cellular Automata, 2010

Размещено на Allbest.ru