2.11 Тест линейной сложности

2.11.1 Суть Теста

Важную роль в этом тесте играет длина линейного регистра с циклическим сдвигом ЛРЦС (LFSR). В тесте необходимо определить - достаточно ли сложна последовательность, чтобы считать её случайной. Случайная последовательность характеризуется длинными ЛРЦС. Короткий ЛРЦС предполагает не случайность последовательности.

2.11.2 Вызов Функции

Lineal-Complexity(M, n), где:

М Длина блока в битах. n Длина битовой строки.

Дополнительные входные данные, используемые функцией, но находящиеся в тексте программы:

Последовательность битов, сгенерированных RNG или PRNG, подвергающиеся тестированию; определена как глобальная структура при вызове функции;

= 1, 2, ... n.

К Число степеней свободы; К = б жёстко закодировано в тесте.

2.11.3 Статистика Теста и Распределение

x2 (obs) величина, показывающая насколько наблюдаемое количество ЛРЦС фиксированной длины соответствует количеству ожидаемых таких ЛРЦС, при предположении, что последовательность случайна.

Основное распределение для статистики – x² распределение.

2.11.4 Описание Теста

(1) п-последовательность разбивается на N независимы блоков по М бит, где n = MN.

(2) Используя алгоритм Берлекампа-Массея5 (Berlekamp-Massey algorithm), определяете линейная сложность L, для каждого из N блоков (i = 1,...,N). L, - это длина само короткой последовательности линейного регистра с циклическим сдвигом (ЛРЦС который генерирует все биты в блоке i. Внутри любой L, последовательности бито суммируя некоторые биты по модулю 2, получаем следующий бит последовательности (бит L1+i).

Например, если М = 13, тестируемый блок - 1101011110001, тогда L, = 4, последовательность получается путём сложения первого и второго бита внутри 4x битовой последовательности, получаем следующий (пятый) бит. Исследование показано далее:

Первые 4 бита и результирующий 5й

Биты 2-5 и результирующий 6й Биты 3-6 и результирующий 7"

Биты 9-12 и результирующий 13й

Biti	Bit 2	Bit3	Bit 4	Bit 5
1	1	0	1	0
1	0	1	0	1
0	1	0	1	1
1	0	1	1	1
0	1	1	1	1
1	1	1	1.	0
1	1	1	0	0
1	1	0	0	0
1	0	0	0	1

Для этого блока пробный алгоритм сдвига работает. Если бы этого не произошло, то другой алгоритм был бы применён к блоку (например, сложение бита 1 и 3, получаем результирующий 5й, или сложение битов 1, 2 и 3, в результате получаем 6й, и т.д.).

(3) Предполагая, что последовательность случайна, посчитаем значение теоретической величины ц:

Например, в данном случае

(4) Для каждой подстроки, вычисляется значение Ti , где

Например, Т, = (-I)¹³ • (4 - 6.777222) + 2/9 = 2.999444.

(5) Записывается значение Т; в ,..., как показано:

Если

Т, < -2.5 Увеличить на единицу

-2 5 < Т; < -1.5 Увеличить на единицу

-1.5 < Tj < -0.5 Увеличить на единицу

-0.5 < Т; < 0.5 Увеличить иа единицу

0.5 < Tj 5:1.5 Увеличить на единицу

1.5 < Т; <. 2.5 Увеличить на единицу

Т, > 2.5 Увеличить на единицу

(6) Вычисляется

(7) Вычисляется

2.11.5 Правило Принятия Решения (с 1 % Уровнем)

Если рассчитанная вероятность P-value < 0.01, тогда считаем, что последовательность не является случайной. Иначе, делаем вывод, что последовательность случайна.