Описание статистического теста.

Опишем статистический тест “Стопка книг”, который составляет основную часть градиентной атаки. Данный статистический тест является критерием согласия на проверку гипотезы о случайности распределения заданной битовой последовательности.

В отличие от многих других тестов, например критерия хи-квадрат, в тесте «стопка книг» подсчитывается не простая частота встречаемости букв в выборке, а частота встречаемости номеров букв в стопке алфавита: перед тестированием множество всех номеров {1, . . . , S} разбивается на две непересекающиеся части: A1 = {1, 2, . . . , K} и A2 = {K+1, . . . , S}. Затем по выборке (x₁, x₂,..., x_N) подсчитывается – количество номеров , принадлежащих подмножеству A₁, т. е. количество попаданий букв в “верхнюю часть” “стопки книг”. Число (N − ), очевидно, равно количеству попаданий в “нижнюю часть” стопки. Далее вычисляется статистика , . Если меньше квантиля хи-квадрат с 1 степенью свободы и уровнем доверия, равным , то последовательность считается случайной, иначе – не случайной. При том, если она не случайна, то значение определим, как числовую «меру случайности» (обозначим её буквой Г).