Введение 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. Ожидаемое количество нулей и единиц
п равно - где п - длина последовательности.
• Независимость. Степень корреляции двух случайных величин в сгенерированной последовательности должна быть мала. При этом рассматриваются любые, а не только рядом стоящие случайные величины.
• Длина периода. Длина максимальной, не содержащей самой себя, числовой цепочки в последовательности случайных чисел должна быть как можно больше.
Естественно возникает вопрос, - в какой среде реализовывать данные тесты, так как в настоящее время существует множество различных языков программирования. Существуют различные нюансы при написании программы. Например, за какое время программа отработает тот или иной тест. Поэтому в данной работе мы проводим анализ производительности стандартных функций в различных языках программирования и математических средах.

Купить