Заказать работу


Тип работы:
Предмет:
Язык работы:


СРАВНИТЕЛЬНЫЙ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ ГЕНЕРАЦИИ СЛУЧАЙНЫХ ВЕЛИЧИН

Работа №77879
Тип работыДипломные работы, ВКР
Предметматематика
Объем работы75
Год сдачи2017
Стоимость4345 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено 9
Не подходит работа?

Узнай цену на написание

Введение 3
Глава 1. Анализ производительности генераторов. Тесты NIST 5
1.1 Анализ производительности генераторов 5
1.2. Пакет тестов NIST 7
1.2.1. Частотный побитовый тест 8
1.2.2. Частотный блочный тест 9
1.2.3. Тест на одинаковые идущие подряд биты 11
1.2.4. Тест на самую длинную последовательность из единиц в
блоке 12
1.2.5. Тест рангов бинарных матриц 14
1.2.6. Спектральный тест 15
1.2.7. Тест на встречающиеся непересекающиеся шаблоны 17
1.2.8. Тест на встречающиеся пересекающиеся шаблоны 19
1.2.9. Тест на линейную сложность 21
1.2.10. Тест на подпоследовательности 23
1.2.11. Приблизительная энтропия 25
1.2.12. Тест кумулятивных сумм 27
1.2.13. Тест на произвольные отклонения 29
1.2.14. Разновидность теста на произвольные отклонения 33
1.3 Результаты тестирования 36
Заключение 37
Список используемых источников 38
Приложение


В настоящее время генераторы случайных чисел используются во многих сферах: наука, методы компьютерного моделирования, машинное обучение, статистика, игры. Основное применение случайных и псевдослучайных чисел - криптография. Например, криптосистемы используют ключ, который должен быть сгенерирован случайным образом. Однако не каждый генератор по-настоящему «хорош». Если последовательность предсказуема, то даже самый стойкий алгоритм шифрования становится уязвимым, т.е. взломать его становится намного проще. К счастью, существует множество способов проверки качества (случайности) получившейся последовательности. Одним из них является пакет тестов NIST.
Статистические тесты NIST - пакет статистических тестов, состоящий из 15 тестов, которые предназначены для проверки случайности двоичных последовательностей произвольной длины, порождаемых либо аппаратными, либо программными генераторами случайных чисел.
NIST представляет из себя комплекс проверок по различным статистическим критериям, включая в качестве основных проверки на:
• Равномерность. Появление битов 0 и 1 в сгенерированной последовательности равновероятно и вероятности их появления приблизительно равны /2. Ожидаемое количество нулей и единиц
п равно - где п - длина последовательности.
• Независимость. Степень корреляции двух случайных величин в сгенерированной последовательности должна быть мала. При этом рассматриваются любые, а не только рядом стоящие случайные величины.
• Длина периода. Длина максимальной, не содержащей самой себя, числовой цепочки в последовательности случайных чисел должна быть как можно больше.
Естественно возникает вопрос, - в какой среде реализовывать данные тесты, так как в настоящее время существует множество различных языков программирования. Существуют различные нюансы при написании программы. Например, за какое время программа отработает тот или иной тест. Поэтому в данной работе мы проводим анализ производительности стандартных функций в различных языках программирования и математических средах.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании студенческих
и аспирантских работ!


Мы рассмотрели оценку эффективности генераторов псевдослучайных величин с точки зрения скорости выполнения программ в разных языках программирования. После сравнения в следующих средах: C++, C#, Java, R, Mathematica мы получили следующие результаты: в случае когда производилась генерация по одному случайному элементу - лучший результат наблюдается в C++.
Также на этом языке была реализована часть пакета статистических тестов NIST для проверки эффективности работы генераторов псевдослучайных величин. Результаты тестирования пакета NIST показали, что генераторы работают вполне корректно.
Случай векторной генерации рассматривался в R и Mathematica. В результате «быстрее» оказался R.
Реализованные программы описаны в приложении.



1. А.Потий, С.Орлова, Т.Гриненко «Статистическое тестирование генераторов случайных и псевдослучайных чисел с использованием набора статистических тестов NIST», 2001г.
2. Сайт «Википедия», статья «Статистические тесты NIST» https://ru.wikipedia.org/
3. Сайт «Habrahabr», статья «Статистическая проверка случайности двоичных последовательностей методами NIST»https: //habrahabr.ru/
4. В.А.Успенский, А.Л.Семенов, А.Х.Шень «Может ли (индивидуальная) последовательность нулей и единиц быть случайной?», 1990г.


Работу высылаем на протяжении 30 минут после оплаты.

Пожалуйста, укажите откуда вы узнали о сайте!


Подобные работы


© 2008-2022 Cервис помощи студентам в выполнении работ