6. Суперпозиция нескольких регистров сдвига. Определение линейной сложности и периода схем,построенных на суперпозиции нескольких регистров сдвига.

 - бесконечная последовательность с членами   – конечная последовательность длины , членами которой вляются  Определение: Линейной сложностью бесконечной двоичной последовательности   называется число , которое определяется следующим образом:

Если  – нулевая последовательность , то 

Если не существует РСЛОС, который генерирует , то  равно бесконечности.

Иначе,  есть длина самого короткого РСЛОС, который генерирует .

Определение: Линейной сложностью конечной двоичной последовательности  называется число , которое равно длине самого короткого Поточные шифры на регистрах сдвига с линейной обратной связью

(РСЛОС), который генерирует последовательность, имеющую в качестве первых  членов . Свойства линейной сложности: Пусть  и  – двоичные последовательности. Тогда: 1. Для любого  линейная сложность подпоследовательности  удовлетворяет неравенствам  2.  тогда и только тогда, когда  – нулевая последовательность длины . 3.  тогда и только тогда, когда . 4. Если  – периодическая с периодом , тогда  5.  Эффективным алгоритмом определения линейной сложности конечной двоичной последовательности является алгоритм Берлекемпа-Месси.