Кpиптогpафия от папиpуса до компьютеpа


Последовательности максимальной длины - часть 3


 

n

 

биты

переноca

 

 

8

1

2

3

8

 

16

0

2

11

16

 

24

0

1

6

24

 

32

0

1

21

32

Известен неприводимый многочлен x**61+x**3+1, a по многочленам больших степеней в литературе данных найти не удалось. Поэтому естественно возникает вопрос: как ведут себя последовательности, порожденные произведением взаимно простых многочленов. Ответ на него дает следующая теорема, доказательство которой мы опустим, так как оно в нашем контексте неинтересно.

ТЕОРЕМА 7. Если f(x) и h(x) - взаимно простые многочлены, то тогда многочлен f(x)*h(x) порождает последовательности, являющихся суммами последовательностей для f(x) и h(x).

Итак, период последовательности от f(x)*h(x) равен произведению периодов соответствующих последовательностей f(x) и h(x). Однако причин для радости мало, так как сюда же входят и последовательности периода 1 для нулевых данных. Приведем пример. Многочлены f(x)=x**3+x+1 и h(x)=x**2+x+1 неприводимы и взаимно просты. В зависимости от начальных данных многочлен f(x) имеет одну последовательность периода 1 и 7 последовательностей периода 7. Многочлен h(x) имеет одну последовательность периода 1 и 3 последовательности длины 3, а многочлен f(x)*h(x) имеет такой спектр периодов:

 

Период

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

 

1*1=1

1*1=1

 

1*3=3

1*3=3

 

1*7=7

1*7=7

 

3*7=21

3*7=21

Таким образом, произведение многочленов дает последовательности с произведением периодов. Ненулевые начальные данные для многочленов максимальных периодов гарантируют получение произведения этих периодов, что должно устроить конструкторов гаммы. В следующей таблице приведены данные о рядах, которые генерируют тестированием всего лишь двух бит.

n

биты

 

 

взаи

мная

прос

тота

пери

одов

 

 

 

 

 

 

17

18

20

21

22

23

25

28

29

31

17

2

17

-

+

+

+




- Начало -  - Назад -  - Вперед -