2.9.5 Правило Решения (на 1%-ом Уровне)

Если вычисленная P-Value- <0.01, затем заключать, что последовательность неслучайна. Иначе, заключите, что последовательность случайна.

2.9.6 Заключение и интерпретация результатов теста

Начиная с P-value, полученной в шаге 5 из Секции 2.9.4 - 0.01 (Р-значение = 0.767189), заключение - то, что последовательность является случайной. Теоретическое ожидающее значение для (р были вычислены как показано в таблице в шаге (5) из Секции 2.9.4. Если отличается значительно от expectedValue (L), то последовательность значительно сжимаема.

2.9.7 Рекомендация входных размеров

Это тест требует длинной последовательности битов (n>. (Q + К) L), которые разделены на две доли L-бита, блокирует, где L должен быть выбран так, чтобы б < L < 16. Первая сегмент состоит из Q блоков инициализации, где Q должен быть выбран так, чтобы Q = 10 • 2L. Второй сегмент состоит из К блоков теста, где К = [n/L] - Q ~ 1000 • 2L. Значения L, Q и п должны быть выбранные следующим образом:

n	L	Q=10*2L
387840	6	640
904 960	7	1280
2 068 480	8	2560
4654080	9	5120
1342 400	10	10240
22753280	11	20480
49 643 520	12	40960
107560960	13	81920
231669760	14	163840
496 435 200	15	327680
1,059,061 760	16	655360

2.9.8 Пример

(вход) = двоичная строка, используемая конструкции G-SHA-14

(вход) n = 1048576, L = 7, Q = 1280

(примечание) примечание: 4 бита отвергнуты.

(обрабатываемая) с =0.591311, = 0.002703, К = 148516, суммируют = 919924.038020

(обрабатываемая) = 6.194107, expectedValue = 6.196251, = 5.725

(выход) Р-значение = 0.427733

(заключение) Начиная с P-value > 0.01, примите последовательность как случайный.

3.9 "Универсальный статистический" тест Моурера

Это тест было введено в 1992 Ueli Морером Отдела Информатики в Университете Принстона. Тест Морера статистический имеет отношение близко со per-bit энтропией потока, который его автор утверждает - "правильная качественная мера для секретного - ключевого источника в шифровальном применении. " Также, тест, как утверждается, измеряет фактическое шифровальное значение дефекта, потому что это "связано с продолжительностью оптимальной стратегии ключевого поиска врага,'" или эффективного ключевого размера системы шифра.

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

Тест - тест типа сжатия "основанное на идее относительно Ziv, что универсальное статистическое тест может базироваться на универсальном источнике, кодирующем алгоритм. Генератор должен передать тест, если и только если его последовательность выхода не может быть сжата значительно, " Согласно Мореру, кодирующий источник алгоритм из-за Lempel - Ziv, "кажется, менее удовлетворен для применения как статистическое тест", потому что это, кажется, трудное определить тест статистический, чье распределение может быть определено или приближено.

Тест требуется длинной (в порядке 10 • 2L + 1000 •2L c 6L16) последовательности битов, которые разделены на два отрезка блоков L-бита (6 S L < 16), Q >10 • 2L) блоки инициализации и К (~ 1000 • 2L) тестовые блоки. Мы берем К= перекрывающий (n/L) — Q, чтобы максимизировать его значение. Заказ(порядок) величины Q должен быть определенно выбран, чтобы гарантировать, что все возможные образцы набора из двух предметов L-бита действительно фактически происходят в пределах блоков инициализации. Тест не удовлетворено за очень большие значения L, потому что инициализация занимает время, показательное в L.

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

Алгоритм достигает этого эффективно subscripting динамический таблица поиска, использующий представление целого числа двойных битов, составляющих блоки шаблона. Стандартизированная версия статистических - стандартизация, предписываемая тестм - является по сравнению с приемлемым диапазоном, основанным на стандартной нормальной (Гауссовской) плотности, используя тестового статистического предназначения, который дается формулой (16) в Морере(1992).

Ожидаемая значение статистического теста - это случайной переменной iog2 Г, где Г = ГЛОССАРИЙ - геометрическая случайная переменная с параметром 1-2-L. Есть несколько версий приблизительных эмпирических формул для разницы формы

Здесь, с (L, К) представляет фактор, который принимает во внимание зависимый характер(природу) возникновений шаблонов. Последний из приближений (Согоп и Naccache (1998): не вложенный в тестовый кодекс набора) имеет форму

Однако, Согоп и Naccache (1998) сообщение, что "погрешность из-за [это приближение] может делать тест в 2.67 раз более разрешающим чем, что теоретически допускают(признают). " Другими словами, отношение стандартного отклонения fn, полученного от приближения выше к истинному стандартному отклонению отклоняется значительно от один. Со связи с вышеизложенным и также так как все приближения базируются на "допустимом" предположении, что Q—>, гипотеза хаотичности может быть проверена, подтверждая(проверяя) нормальность наблюдаемых(соблюденных) ценностей предполагая, что разница является неизвестной. Это может быть сделано, используя t-тест.

Первоначальная(Оригинальная) последовательность должна быть разделена в г (г <= 20) подвереницы, на, каждый из которых значение универсального тесты статистический оценена (за ту же самую значение параметров К, L и Q). Типовая разница оценена, и Р — value

Универсальный статистический тест Маурера