3.12 Серийный тест
(Обобщенный) серийный тест представляет собой совокупность процедур, основанных на проверке равномерности распределения битовых комбинаций данной длины.
В частности, пусть i1,…im - вектор из 0 и 1 длины т, последовательно принимающий все возможные 2m значений, v i1,…im - частота комбинации ( i1,…im) в
«закольцованной»
битовой строке (
)-Далее
вычисляется
Таким
образом,
- это статистика типа x2,
но считать, что
, имеет распределение x2
- это распространенная ошибка. В
действительности частоты v i1,…im;
, не независимы.
Соответствующие обобщенные серийные статистики для тестирования случайности (Kimberley (1987), Knuth, D. Е. (1998), Menezes, van Oorschot and Vanstone, (1997)) имеют вид
(Здесь
=0.)
Тогда
,
имеет распределение x2
с 2m-1
степенями свободы, а
имеет распределение x2
с 2m-2
степенями свободы. Следовательно, для
малых значений m, m
можно найти соответствующие значения
P-value по стандартным формулам.
Результат
вычисления
и подсчета частот неправильно указан
в Menezes, van Oorschot and Vanstone (1997) на стр. 181,
формула (5.2): +1 следует заменить на -1.
Сходимость
к распределению x2
была доказана в Good (1953).
Ссылки по тесту
[11 1.1. Good (1953), "The serial test for sampling numbers and other tests for randomness,"
Proc. Cambridge Philos. Soc.. 47. pp. 276-284,
[21 M. Kimberley (1987), comparison of two statistical tests for keystream sequences,"
Electronics Letters. 23, pp. 365-366.
[31 D. E. Knuth (1998), The Art of Computer Programming. Vol. 2, 3rd ed. Reading; Addison-
Wesley, Inc., pp. 61-80.
[41 A. .1. Menezes, P. C. van Oorschot, and S. A. Vanstone (1997), Handbook of Applied
Cryptography. BocaRaton, FL: CRC Press, p. 181.
2.13 Тест аппроксимация энтропии
2.13.1 Цель теста
Как и в предыдущем тесте Секции 2.12, основой этого теста является частотой всех возможных, перекрывающих m-элементных промежутков формируют целую последовательность. Цель теста сравнить частоту перекрытия блоков двух смежных длин против ожидаемого результата для произвольной последовательности.
2.13.2 Вызов функции
ApproximateEntropy (m,n), где
m длина каждого блока, в выбранном случае в m мы подставим первоначальную длину блока, m+1 начало второго блока, n общая длина последовательности. Дополнительно вводится и используется функция, которая вставляется в код теста.
последовательность
элементов сгенерированных для тестирования
RNG или PRNG, эта глобальная структура
созданная к моменту начала вызова
функции.
2.13.3 Тестирование статистического и эталонного распределения.
X2 (obs): По мере того как будет изменяться аргумент АрЕn(m) (шаг в секции 2.13.4) мы получаем оценку ожидаемой величины. Описание распределения для статистики теста является распределение x2.
2.13.4 Описание теста.
Аргументы:
1) N битная последовательность и созданные n возможных m-битных последовательностей, которые начинаются с m-ного элемента и дополняются последующими m-1 элементами, в случае, если достигнут конец последовательности, элементы выбираются с начала последовательности.
Например, если е = 0100110101 и m = 3, тогда n = 10. Добавляем ноль или единицу сначала до конца последовательности. Получаем последовательность для теста 010011010101. (Для каждого значения m.)
2) Частота вхождения п возможных блоков (например, если блок включенный в промежуток от еj до ej+m-i сопоставляется времени j, тогда блок от еj+1 до ej+m-i сопоставляются времени j+1). Пусть счетчик возможных m битных (m+1 битных) последовательностей будет представлен как Сmi, где i значение m бита.
Например для этой последовательности, возможны n блоков (для m=3) 070, 700, 007, 077, 770, 707, 070, 707, 070, и 707, Подсчет вхождений для 2m= 2з =8 возможных m-битных строк определен следующим образом:
#000 = 0, #001 = 7, #010 - 3, #011 = 7, #100 = 7, #101 = 3, #110 - 7, #111 = 0
3) Рассчитаем Cmi=#l/n для каждого значения i. Как пример для этой секции
Для примера в этой секции,
5) Повторим шаги 1-4, поменяем m на m+1.
Шаг 1: Для рассматриваемой секции, m на данный момент 4, последовательность для теста 0100110101010.
Шаг 2: Возможные блоки 0100, 1001, ОО11, О11О, 1101, 1010, 0101, 1010, 0101, 1010. Подсчет вхождений: #0011 = 1, #0100 = 1. #0101 = 2, #0110 =1,#1001 =1, #1010=3, #1101 = 1, и О для всех остальных.
6) Рассчитаем статистику . теста x2 = 2n[log 2 - ApEn(m)], где
ApEn(m)=
Для этой секции
АрЕn(З) = -1.643418-(-1.834372) = 0.190954
X2 - 2-10(0.693147-0.190954) = 0.502193
7)
Рассчитаем значение Р = igamc (2m-1,
)
Для
этой секции значение Р = igamc(22,
)
= 0.261961.
2.13.5. Правило решения (от 1%)
Если полученное значение Р<0.01, тогда последовательность не случайная, иначе-случайная.
2.13.6. Исследование и интерпретация результатов теста
Значение Р, полученное после выполнения шага 7 из Секции 2.13.4
0,01 (Р= 0.261961), следовательно, последовательность случайна.
Малое значение АрЕп(т) должно подразумевать более сильную
закономерность (смотри шаг 6 с Секции 2.13.4). Большие значения должны
подразумевать (надежные) колебания и нерегулярность.
2.13.7. Рекомендуемая водимая размерность.
Выбор
тип рекомендуется m
[log2
n] - 2.
2.13.8. Пример.
Введено:
=
1100100100001111110110101010001000100001011010001100001000110100110 001001100011001100010100010111000
m=2; n=100;
вычислено
АрЕn(m) =0.665393
X2(obs) =5.550792
P= 0.235301
Выводы
Так как Р >0.01, допустим что последовательность случайная.
3.13. Тест аппроксимации энтропии.
Характеристики
аппроксимации энтропии основываются
на повторении образцов строк. Если
Yi(m)=(
).
определим
где Сmi- относительная частота вхождений образцов Yi(m) в строке, и Ф(m)
энтропия эмпирического распределения, возникающего в наборе всех возможных (2m) образцов длины m.
Аппроксимация
энтропии АрЕn
для порядка m,
m
1 определим как
АрЕn
(n)
=
, где АрЕп (0) = -Ф(-1)
.
«АрЕn(m) мера логарифм частоты с блоком длинной m тот закрыт вместе оставаться закрыт вместе для блока расширенного на одну позицию. Таким образом, малое значение АрЕn(m) должно подразумевать более сильную закономерность, неизменность последовательности. Напротив, большие значения должны подразумевать (надежные) колебания и нерегулярность. (Pincus and Singer, 1996, p. 2083).
Pincus
и Kalman (1997) определили что последовательность
будет m-нерегулярна,
(m-случайна)
если аппроксимация энтропии АрЕn(m)
будет больше вероятного(возможного
значения). Они оценили качество АрЕn(тm,
m=0,1,2
для бинарных и десятичных расширений
(наборов ?) для
для случайных последовательностей, где
демонстрация для
более нерегулярна нежели для
.
Для
фиксированных блоков длинной m, должна
существовать достаточно длинная
нерегулярная строка, ApEn(m)
log2.
Предельное распределение для n[log2
- АрЕn(m)]
совпадает с x2
-случайным значением с 2m
степенями свободы. Этот факт составляет
основу статистического теста и был
доказан (открыт ?) Rukhin (2000)
Таким образом x2 (obs) = n[log 2 - ApEn(m)], определяет
P=igamc(2m-1,x2(obs)/2).
Актуально что, предельное распределение аппроксимации энтропии может использоваться для модификации определения как
Определим изменение аппроксимации энтропии как
По
Jensen's изменение
для
любых m, принимая во
внимание
возможность
.
Следовательно, наибольшее возможное
значение для изменения энтропии log s,
достигается при n=sm,
и распределение всех m образцов одинаково
(равно). Когда рассчитаем аппроксимацию
энтропии для нескольких значений m, это
будет достаточно для получения суммы
всех частот для т-шаблонов равных n.
Когда п велико, тогда АрЕn(m) и измененная версия не очень отличается
Действительно
для
постоянных m, ф(m)
,
должно быть закрыто (сходиться ?) для
больших
п. Следовательно, аппроксимация энтропии по Pincus' и измененная версия
должны сходиться (быть закрыты), и их асимптотические распределения
должны совпадать.
Справочная информация для теста.
[1] S. Pincus and В. Н. Singer, VRandomness and degrees of irregularity, "Proc.
Natl. Acad. Sci. USA. Vol. 93, March 1996, pp. 2083-2088.
[2] S. Pincus and R. E. Kalman, \Not all (possibly) \random" sequences are created
equal," Proc. Natl. Acad. Sci. USA. Vol. 94, April 1997, pp. 3513-3518.
[3] A. Rukhin (2000), \Approximate entropy for testing randomness," Journal of
Applied Probability. Vol. 37, 2000.