Читать онлайн «Булевы функции в теории кодирования и криптологии»

ИНФОРМАЦИОННАЯ БЕЗОПАСНОСТЬ: КРИПТОГРАФИЯ Институт проблем информационной безопасности МГУ Логачёв О. А,, Сальников А1 А. , Ященко В. В. Булевы функции в теории кодирования и криптологии Москва Издательство МЦНМО 2004 УДК 519-6 (082) ББК 22. 18 Л69 Издание осуществлено при поддержке РФФИ {издательский проект № 03-01-14062) Логачёв О. А. , Сальников А. А. , Ященко В. В. Л69 Булевы функции в теории кодирования и криптологии — М. : МЦНМО, 2004. — 470 с. ISBN 5-94057-117-4 В книге впервые на русском языке в систематическом виде изложены криптографические и теоретико-кодовые аспекты использования аппарата теории булевых функций. Исключение составили лишь вопросы, связанные с теорией сложности и решением систем булевых уравнений. При этом в книге нашли своё отражение как классические результаты, так и результаты, опубликованные в последнее время. Для понимания книги достаточно сведений, имеющихся в университетских курсах по линейной алгебре, теории групп, теории конечных полей и полиномов, комбинаторике и дискретной математике. Помимо этого предполагается знакомство с основами теории вероятностей. Основой для книги послужили материалы курсов, читаемых авторами в МГУ для студентов механико-математического факультета и факультета вычислительной математики и кибернетики, специализирующихся по направлению «Информационная безопасность». Книга будет полезна студентам, аспирантам и научным работникам, интересующимся дискретной математикой, теорией кодирования и криптологией. Она может быть использована в том числе и как справочник. ББК 22. 18 ISBN 5-94057-117-4 9"785940"571179 © Логачёв О. Д. , Сальников А. А. , Ященко В. В. , 2004. © МЦНМО, 2004. Оглавление Предисловие 8 От авторов 9 Обозначения 11 Глава 1. Арифметика конечных полей и полиномов 16 §1. 1. Алгебраические основы 16 § 1. 2. Строение конечных полей 41 § 1. 3. Полиномы над конечными полями 54 Комментарии к главе 1 63 Глава 2. Булевы функции 65 § 2. 1. Основные понятия и определения 65 §2. 2. Числовые и метрические характеристики 74 §2. 3. Автокорреляция и взаимная корреляция 90 §2. 4. Групповая алгебра булевых функций 97 §2. 5. Криптографические свойства булевых функций и отображений 101 §2. 6. Покрывающие последовательности булевых функций 114 Комментарии к главе 2 118 Глава 3. Классификации булевых функций 119 §3. 1. Групповая эквивалентность отображений. Теорема Пойа . . 119 §3. 2. Классификация булевых функций от пяти переменных ... . 128 §3. 3. Классификация квадратичных булевых функций 138 §3. 4. Классификация однородных кубических форм от 8 переменных 148 §3. 5. /?А1-эквивалентность булевых функций 152 Комментарии к главе 3 156 Глава 4. Линейные коды над полем F2 158 §4. 1. Основные свойства линейных блочных кодов 158 § 4. 2. Задача декодирования 170 § 4. 3. Циклические коды 176 §4. 4. Некоторые классы примитивных циклических кодов . 191 Комментарии к главе 4 199 Оглавление Глава 5. Коды Рида—Маллера 200 §5. 1. Общие свойства кодов Рида—Маллера 200 § 5. 2. Алгоритм декодирования Рида 210 §5. 3.