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


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


ТЕОРЕМА 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).




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