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


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


Естественно, что желательно получить как можно более длинный период последовательности от многочлена заданной степени. Ответ на вопрос, каков максимальный период, получаемый от последовательности, мы уже имеем - не больше 2**N-1 в GF(2^). Можно было бы и поверить в существование примитивных многочленов, порождающих такие последовательности. Тем не менее, желательно иметь процедуру, позволяющую находить такие многочлены пусть не практически, то хоть теоретически, если они только существуют. Поэтому приведем теорему:

ТЕОРЕМА 5. Если многочлен f(x) степени n делит многочлен х**k-1 лишь при k>2**n-1, то период его любой ненулевой последовательности равен 2**n-1.

Пусть f(x) делит многочлен х**k-1 при k=2**n-1, тогда длина периода любой, порожденной им ненулевой последовательности делит 2**N-1. Если 2**N-1 простое число, то последовательность максимального периода обеспечена. Иначе допустим, что длина периода некоторой последовательности равна k

Например, многочлен х**4+х+1 делит х*15+1, но не делит ни один многочлен х**K-1 при k        

Gi+G(i-1)+G(i-4)=0

При разных его начальных значениях генерируется такие последовательности:
     0001=>(000111101011001), 0010=> (001000111101011),
     0011=> (001111010110010) и т. д.
     Все они в соответствии с теорией имеют длину периода 15 и отличаются друг от друга лишь сдвигом. Из этого вытекает очень важное для криптографии свойство последовательностей максимального периода, что их одиночный период состоит из всех разных неповторяющихся ненулевых блоков длины n, что гарантирует хорошие статистические качества получаемых псевдослучайных чисел. В частности, такие последовательности не имеют скрытой периодичности, на чем следует остановиться несколько подробнее. Иногда последовательности такого вида с максимальным периодом называют последовательностями Де Брюйна в честь исследователя, подробно описавшего в открытой научной печати их свойства.




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