1. Цел и теста
Принцип этого теста - число отличных слов в последовательности. Цель испытания состоит в том, чтобы определить, как далеко проверенная последовательность может быть сжата. Последовательность, как рассматривается, является неслучайной, если это может быть сжато. Случайная последовательность будет иметь характерное число отличных образцов.
2. Вызов функции
LempelZivCompression (n), где:
nдлина битовой последовательности. Дополнительный вход,
используемый функцией, но снабженный кодом теста;
е последовательность частиц как произведено RNG или проверяемым
PRNG существует как глобальная структура во время запроса функции;
е=е1, е2, ...
3. Тестовая статистика
На распределение Wobs. число непересекающихся и кумулятивно отличных
слов в последовательности. Распределение ссылки для испытания - нормальное
распределение.
4. Описание теста
(1) Разбивается последовательность на последовательные, непересекающиеся и отличные слова, которые формируют "словарь" слов в последовательности. Это выполняется созданием под последовательности частиц исходной последовательности. Заканчивающаяся под последовательность - новое слово в словаре. Wobs= число различных слов. Например, если е==010110010, тогда экспертиза продолжается следующим образом:
Получаем пять слов в словаре: 0, 1,01, 10, 010. Wobs = 5.
(2) Вычисляем P-value = 0.5*erfc((m - Wobs)/sqrt(2s2)) т, где т = 69586.25 и s=70.448718 при п = l(f . Для других значений n, значения m и s должны быть рассчитаны. Обратите внимание, что, так как никакая известная теория не доступна, чтобы определить точные значения m и s, эти величины были вычислены (согласно предположению о хаотичности) с использованием SHA-1. Blum-Blum-Shub генератор даст подобные результаты для m и s2. Поскольку пример в этой секции — намного короче чем рекомендуемая длина, величины для m и s2 не имеют силы. Вместо этого, предположим, что испытание проводилось на последовательности миллиона частиц, и количество Wobs= 69600 было получено.
5. Правила решения
Если вычисленная величина Р-value < 0.01, тогда заключает, что последовательность неслучайна. Иначе, заключите, что последовательность случайна.
6. Заключения и интерпретация результатов тестирования
Начиная с P-value, полученной в шаге 2 секции 2.10.4 являются > 0.01 (Р-value = 0.949310), заключение - то, что последовательность является случайной. Обратите внимание, что для n = 106, если бы Wobs упал ниже 69,561, тогда заключение было бы то, что последовательность является сжимаемой и, поэтому, не случайной.
7. Рекомендации размера на входе
Рекомендуется, чтобы каждая последовательность, которая будет проверена состояла из минимум 1,000,000 частиц (1,000,000-бит).
Этот тест сжимает случайную последовательность, используя алгоритм Лемпеля-Зива. Если сокращение статистически значительно, когда сравнено с теоретически ожидаемым результатом, последовательность, как объявляют, является неслучайной. Чтобы проверить генератор, много последовательностей должны быть проверены таким образом. Значения вероятности рассчитаны для каждой последовательности, и гипотезы, что значения вероятности однородно распределены, проверены, например, тестом Колмогорова-Смирнова. Тест подобен испытанию энтропии и даже более подобное универсальному статистическому тесту Маурера. Однако, тест Лемпеля-Зива непосредственно включает сжатие эвристически. Есть несколько разновидностей алгоритма. Тест, используемый здесь предполагает, что fn- двойная последовательность, и определяется следующим образом:
1. Просматривается последовательность и разбивается на последовательные непересекающиеся слова так, чтобы следующее слово было самой короткой нитью, среди еще не замеченных.
2. Слова нумеруются последовательно.
3. Каждое слово состоит из префикса и суффикса; префикс - номер предыдущего слова, которое соответствует всему кроме последней цифры; суффикс - последняя цифра. Возможно, что для маленького п, сжатие является более длинным чем первоначальное представление. После работы Олдоса, W(n) представляют число слов в двоичной случайной последовательности длины п. Они показывают, что слов в сжатии Лемпеля-Зива. Однако Олдос был неспособен определить ценность i [W (п)]. Эта сложность была преодолена Kirschenhofer, Prodinger, и Szpankowski (1994), которые'доказывают, что
Необходимо пройти полное декодирование. W используется, чтобы вычислить z, которое определяется по сравнению со стандартным нормальным распределением. Тест односторонний, так как некоторые скопированные последовательности фактически являются также сжатыми
Изучение
моделирования с использованием
Blum-Blum-Shub генератора (1986) установило, что
сжатие не полезно для последовательностей
длины меньше чем 10 миллионов. Точность
оценки зависит от хаотичности используемого
генератора. Blum-Blum-Shub генератор был
выбран, потом что его хаотичность
эквивалентна математической факторизации.
P-value вычислена как
