Интернет магазин китайских планшетных компьютеров


Компьютеры - Тестирование псевдослучайных последовательностей - Статистические тесты

23 января 2011


Оглавление:
1. Тестирование псевдослучайных последовательностей
2. Графические тесты
3. Статистические тесты
4. Практические приложения



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

№ Название Автор Организация
1 Тесты NIST Andrew Rukhin, et. al. NIST ITL
2 TEST-U01 P.L’Ecuyer и др. Universit´e de Montr´eal
3 CRYPT-X Helen Gustafson и др. Queensland University of Technology
4 The pLab Project Peter Hellekalek University of Salzburg
5 DIEHARD George Marsaglia Florida State University
6 Dieharder Robert G. Brown Duke University
7 ENT John Walker Autodesk, Inc.
8 The Art Of Computer Programming Vol. 2 Seminumerical Algorithms Дональд Кнут Stanford University
9 Handbook of Applied Cryptography Alfred Menezes и др. CRC Press, Inc.

Тесты DIEHARD

Тесты DIEHARD были разработаны Джорджем Марсальей  в течение нескольких лет и впервые опубликованы на CD-ROM, посвящённом случайным числам. Они рассматриваются как один из наиболее строгих известных наборов тестов.

Тесты Д. Кнута

Тесты Кнута основаны на статистическом критерии χ. Вычисляемое значение статистики χ сравнивается с табличными результатами, и в зависимости от вероятности появления такой статистики делается вывод о ее качестве. Среди достоинств этих тестов — небольшое их количество и существование быстрых алгоритмов выполнения. Недостаток — неопределенность в трактовке результатов. Вот краткое описание этих тестов:

  • Проверка несцепленных серий. Последовательность разбивается на m непересекающихся серий и строится распределение χ для частот появления каждой возможной серии.
  • Проверка интервалов. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя длины подпоследовательностей, все элементы которых принадлежат определённому числовому интервалу.
  • Проверка комбинаций. Последовательность разбивается на подпоследовательности определённой длины, и исследуются серии, состоящие из различных комбинаций чисел.
  • Тест собирателя купонов. Пусть \xi_1, \xi_2, \dots, \xi_n — последовательность длины n и размерности m. Исследуются подпоследовательности определённой длины, содержащие каждое m-разрядное число.
  • Проверка перестановок. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя взаимное расположение чисел в подпоследовательностях.
  • Проверка на монотонность. Служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей.
  • Проверка корреляции. Данный тест проверяет взаимонезависимость элементов последовательности.

Тесты NIST

Отличие этих тестов от других современных — открытость алгоритмов. Также среди достоинств — однозначная интерпретация результатов тестирования. Таблица общих характеристик:

№ Название теста Определяемый дефект
1 Частотный тест Слишком много нулей или единиц
2 Проверка кумулятивных сумм Слишком много нулей или единиц в начале последовательности
3 Проверка «дырок» в подпоследовательностях Отклонение в распределении последовательностей единиц
4 Проверка «дырок» Большое число подпоследовательностей нулей и единиц свидетельствует, что колебание потока бит слишком быстрое
5 Проверка рангов матриц Отклонение распределения рангов матриц от соответствующего распределения для истинно случайной последовательности, связанное с периодичностью последовательностей
6 Спектральный тест Периодические свойства последовательности
7 Проверка непересекающихся шаблонов Непериодические шаблоны встречаются слишком часто
8 Проверка пересекающихся шаблонов Слишком часто встречаются m-битные последовательности единиц
9 Универсальный статистический тест Маурера Сжимаемость последовательности
10 Проверка случайных отклонений Отклонение от распределения числа появлений подпоследовательностей определённого вида
11 Разновидность проверки случайных отклонений Отклонение от распределения числа появлений подпоследовательностей определённого вида
12 Проверка аппроксимированной энтропии Неравномерность распределения m-битных слов. Малые значения означают высокую повторяемость
13 Проверка серий Неравномерность распределения m-битных слов
14 Сжатие при помощи алгоритма Лемпела-Зива Большая сжимаемость, чем истинно случайная последовательность
15 Линейная сложность Отклонение от распределения линейной сложности для конечной длины подстроки


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


<<< Схема Шнорра


Компьютерное аппаратное обеспечение   
Вычислительные комплексы   
Компьютерные данные   
Компьютерные журналы   
Классы компьютеров   
Компьютеры   
Программное обеспечение   
Производители компьютеров   
Профессии в ИТ   
Системное администрирование   
Компьютерный сленг   
Списки компьютерных терминов   
Человеко-компьютерное взаимодействие