Последовательности максимальной длины
Естественно, что желательно получить как можно более длинный период последовательности от многочлена заданной степени. Ответ на вопрос, каков максимальный период, получаемый от последовательности, мы уже имеем - не больше 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, что гарантирует хорошие статистические качества получаемых псевдослучайных чисел. В частности, такие последовательности не имеют скрытой периодичности, на чем следует остановиться несколько подробнее. Иногда последовательности такого вида с максимальным периодом называют последовательностями Де Брюйна в честь исследователя, подробно описавшего в открытой научной печати их свойства.
ТЕОРЕМА 6. Если S - последовательность максимального периода, то она имеет равномерный спектр.
Если S - последовательность максимального периода, то она состоит из 2**(N-1)-1 нулей и 2**(N-1) единиц. Последовательность {(Si*Si+j)} при любом j>0 представляет собой сдвиг исходной последовательности, а при j=0 состоит Из 2**N-1 единиц. Таким образом, автокорреляционная функция R равна: 2**N-1 при j=0 и 0 при j>0. А, поскольку Rj представляет собой дельта-функцию, то ее спектр равномерный и последовательность этим похожа на случайный белый шум.
Теперь мы знаем, что грех искать лучший материал для псевдослучайных последовательностей, чем рекуррентные последовательности описанного вида. Они обладают исключительным набором свойств: предельно большая длина периода, отсутствие скрытых периодичностей, статистическая равномерность, что делает их незаменимыми в криптографии. Однако читатель, искушенный в математике, скорее будет огорчен, чем обрадован предыдущим изложением. И вот почему: мы рассуждали о замечательных свойствах последовательностей, существование которых не доказано. Придется лишь поверить в существование неприводимых многочленов любой степени и, значит, соответствующих им последовательностей, потому что это дается в самом красивом и, наверное, самом сложном из разделов чистой математики теории Галуа. Вот что о ее авторе сообщает Большой энциклопедический словарь:
ГАЛУА (Galois) Эварист (1811-32), франц. математик. Тр. по теории алгебр, ур-ний положили начало развитию современной алгебры. С идеями Г. связаны такие ее важнейшие понятия, как группа, поле и др. Науч. наследие Г. - небольшое число весьма кратко написанных работ, из-за новизны идей не понятых при жизни Г. Опубл. в 1846 Ж. Лиувиллем.
Нельзя не отметить, что теория Галуа представляет собой жемчужину современной математики. Согласно преданию, Эварист Галуа в ночь на 30 мая 1832 года перед дуэлью вместе с письмом другу написал на 41 странице работу, обессмертившую его имя и получившую название теории Галуа. Одна бессонная ночь двадцатилетнего французского гения навеки обрекла миллионы студентов на хроническую бессонницу перед экзаменом по этому предмету, и многие из них будут сетовать на черствость подруги Эвариста, оставившей его в ночь перед дуэлью безутешным, хотя стрелялся он из-за нее. Злые языки утверждают, что разработанная им теория представляет собой акт мести системе высшего образования за то, что его дважды срезали на вступительном экзамене по математике в Политехнической школе. Для нас важно лишь то, что этот гениальный юноша создал теорию, доказывающую существование многочленов, дающих последовательности максимального периода сколь угодно большой степени. Таким образом, в существование их поверить можно. А вот нахождение таких многочленов до сих пор покрыто мраком. Без сомнения, криптографические службы высокоразвитых стран работали и работают над поиском многочленов как можно более высокой степени, но свои последние результаты они почти не освещают в открытой печати. Хуже всего дела идут в России, где не было ни одной открытой публикации отечественных полиномов высокой степени пригодных для помехоустойчивого кодирования и криптографии и колоссальные средства налогоплательщиков оказались, по образному выражению Балоуна из "Бравого солдата Швейка", в сортире. Поэтому приведем старые и открытые данные из демократических стран. В следующей таблице приведены номера 4 бит, которые можно использовать при генерации последовательностей максимальной длины для случайных чисел длиной 8, 16, 24 и 32 бита, то есть для целого числа байт в памяти ЭВМ. Эти биты задают коэффициенты неприводимых многочленов ненулевой степени над GF(2).
| n | биты | переноca | |||
| 8 | 1 | 2 | 3 | 8 | |
| 16 | 0 | 2 | 11 | 16 | |
| 24 | 0 | 1 | 6 | 24 | |
| 32 | 0 | 1 | 21 | 32 |
ТЕОРЕМА 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 | биты |
