P(S>t, H0 истинно) = P(H0 отклоняется/H0 истинно) – вероятность ошибки 1-го рода, P(S t, H0 ложно) = P(H0 принимается/H0 ложно) – вероятность ошибки 2-го рода, где S – значение тестовой статистики, t – критическое значение.

Тестовая статистика используется для вычисления значения P-тест,value, которое суммирует силу доказательств против нулевой гипотезы H0. Другими словами P-тест,value – это вероятность того, что совершенный генератор случайных чисел произведет последовательность менее случайную, чем тестируемая. Если P-тест,value = 1, то тестируемая последовательность считается абсолютно случайной. Если P-тест,value = 0, то тестируемая последовательность считается абсолютно неслучайной.

Для теста выбирается уровень значимости . Если P-тест,value , то нулевая гипотеза H0 принимается, т.е. последовательность считается случайной. Если P-тест,value < , то нулевая гипотеза H0 отвергается, т.е. последовательность считается неслучайной. Обычно выбирается из диапазона [0,001;0,01]. Значение = 0,01 означает, что одна последовательность из 100 будет отвергнута тестом, при том, что эта последовательность действительно случайна. P-тест,value 0,01 означает, что последовательность будет считаться случайной с уверенностью 99%. P-тест,value < 0,01 означает, что последовательность будет считаться неслучайной с уверенностью 99%.

Набор статистических тестов НИСТ

Как уже отмечалось выше, набор статистических тестов НИСТ содержит 16 тестов. Рассмотрим каждый из них подробнее.

Частотный тест

Цель частотного (монобитного) теста (frequency test) – определить является ли число единиц и нулей в последовательности приблизительно таким же, как и в случайной последовательности. Другими словами этот тест оценивает близость доли единиц к 1/2, т.е. число единиц и нулей в тестируемой последовательности должно быть примерно одинаковым.

Для тестируемой двоичной последовательности длиной n бит вычисляется тестовая статистика sobs

sobs Snn ,

где Sn – разница между числом появления единиц и нулей в тестируемой двоичной последовательности.

Затем вычисляется значение P-тест,value

228

P-тест,value = erfc sobs ,

2

где erfc x	2
				e x2 dx – дополнительный интеграл вероятностей [53_Корн].
				x

Малое значение P-тест,value (< 0,01) указывает на то, что в тестируемой последовательности либо слишком много единиц, либо наоборот – слишком много нулей.

Частотный тест внутри блока

Цель частотного теста внутри блока (frequency test within a block) – определить, равно ли число единиц в M-битовом блоке примерно M/2, как в случайной последовательности. При M = 1 этот тест вырождается в частотный тест.

n

Тестируемая

двоичная

последовательность длиной n бит разбивается на

N

M

непересекающихся блоков длиной M бит каждый. Оставшиеся биты отбрасываются.

Вычисляется тестовая статистика

2

N

1

2

obs 4M i

2

,

i 1

где i – доля единиц в каждом M-битовом блоке.

Затем вычисляется значение P-тест,value

igamc N

,

2

obs

P-тест,value =

,

2

2

где igamc(a, x) = a

– неполная гамма-функция,

x

1

e

t t a 1dt

a e t t a 1dt – гамма-функция.

0

Малое значение P-тест,value (< 0,01) указывает на большое отклонение от равной порции единиц и нулей по крайней мере в одном из блоков.

Тест последовательностей

Цель теста последовательностей (the runs test) – определить равно ли количество серий единиц и нулей различной длины количеству аналогичных серий в случайной последовательности.

229

Для тестируемой двоичной последовательности длиной n бит сначала вычисляется доля

12

единиц. Если 2 n , то считается, что тестируемая последовательность

провалила тест последовательностей. Вычисляется тестовая статистика

n 1

Vn obs r k 1,

k 1

где

0, ïðè

k

k 1

, k – k-ый элемент тестируемой последовательности.

1, ïðè

k

k 1

r k

Затем вычисляется значение P-тест,value

Vn obs

2n 1

P-тест,value = erfc

.

2 2n 1

Большое

значение

тестовой статистики Vn(obs) означает, что колебания (изменения

единицы на ноль и наоборот) в последовательности слишком быстрые, маленькое значение тестовой статистики Vn(obs) наоборот означает, что колебания слишком медленные.

Тест наибольших последовательностей единиц в блоке

Цель теста наибольших последовательностей единиц в блоке (test for the longest-run-of- ones in a block) – определить совпадает ли длина самой длинной серии единиц в тестируемой последовательности с аналогичной длиной в случайной последовательности. Отклонение от нормы в ожидаемом размере самой длинной серии единиц означает, что такое же отклонение есть в ожидаемом размере самой длинной серии нулей. Поэтому можно ограничиться только тестом для единиц.

		n
Тестируемая двоичная последовательность длиной n бит разбивается на	N
		M
непересекающихся блоков длиной M бит каждый.

Составляется таблица (таблица 2.15), содержащая частоты появления vj серий единиц

длиной l.
					Таблица 2.15
	vi	M = 8	M = 128	M = 104
	v0	l 1	l 4	l 10
	v1	l = 2	l = 5	l = 11
	v2	l = 3	l = 6	l = 12
	v3	l 4	l = 7	l = 13
	v4		l = 8	l = 14
	v5		l 9	l = 15
	v6			l 16

Вычисляется тестовая статистика

230

K	vi N i	2
2 obs			.
	N i
i 0

Значения для i можно найти в [6].

Значения величин Kи N определяются значением M в соответствии с таблицей 2.16.

											Таблица 2.17
								M	K	N
								8	3	16
								128	5	49
								104	6	75
Затем вычисляется значение P-тест,value
	igamc K	,		2	obs
P-тест,value =								,
					2
	2

Большие значения χ2 указывают на то, что в тестируемой последовательности есть скопления единиц.

Тест рангов двоичных матриц

Цель теста рангов двоичных матриц (the binary matrix rank test) – исследовать линейную зависимость между подстроками (фиксированной длины) тестируемой последовательности.

Тестируемая двоичная последовательность длиной n бит разбивается на		n
	N
		MQ

непересекающихся блоков длиной M Q бит каждый. Каждый M Q-бит блок представляется в виде матрицы размером M Q. Каждая строка матрицы последовательно заполняется Q- битовыми блоками тестируемой последовательности.

Для каждой матрицы вычисляется ранг Rl, l = 1, …, N. Вычисляется тестовая статистика

	2 obs	FM 0,2888N 2		FM 1 0,5776N 2		N FM FM 1 0,1336N 2	,
		0,2888N		0,5776N		0,1336N

где FM равно количеству матриц с рангом Rl = M (полный ранг), FM–1 равно количеству матриц с рангом Rl = M–1, (N – FM – FM–1) – количество остальных матриц.

Затем вычисляется значение P-тест,value

	igamc	1,		2	obs
P-тест,value =
						.
					2

Большие значения χ2(obs) (и, следовательно, маленькие P-тест,value) будут указывать на отклонение распределения рангов от соответствующего случайной последовательности.

231