Современные информационные технологии/2. Вычислительная техника и программирование

Мякенький Артём Вячеславович

Национальный горный университет, Украина

Сравнительный анализ алгоритмов генерации случайных чисел

Современная информатика широко использует случайные и псевдослучайные числа в самых разных приложениях.

Наиболее распространенные сферы применения случайных чисел:

- Имитационное моделирование;

- Криптография;

- Игровая индустрия;

- Решение прикладных математических задач.

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

Для обеспечения безопасности компьютерных систем критически важно иметь алгоритмы, удовлетворяющие такому критерию как непредсказуемость. Иными словами, даже зная алгоритм генератора и все предыдущие элементы последовательности, вычисление следующих элементов должно быть максимально трудоемким.

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

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

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

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

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

В разработанном программном обеспечении были использованы следующие наиболее известные и распространенные алгоритмы:

• "Середины квадрата" фон Неймана;

• Линейный конгруэнтный;

• Фибоначчи с опозданием;

• Алгоритм Блюма - Блюма - Шуба

• Вихрь Мерсенна.

Для сравнительного исследования статистической качества данных алгоритмов был использован теоретический критерий оценки качества «хи-квадрат». В ходе разработки программного продукта было использована среда программирования Borland Delphi 7.

Источниками проведения экспериментальных исследований являются:

• справочная литература;

• научная литература;

• техническая литература;

• программная документация.

Литература

1. Гмурман, В.Е. "Руководство к решению задач по теории вероятностей и математической статистике": Учеб. пособие — 11-е изд., перераб. - М.: Высшее образование, 2006.-404 с.

2. Крамер Г. Математические методы статистики. – М.: Мир, 1975. – 648 с.

3. Свободная Интернет-энциклопедия

4. Исходные коды реализации различных алгоритмов