/
Автор: Нечаев В.И.
Теги: теория чисел математика криптография учебное пособие защита информации
ISBN: 5-06-003644-8
Год: 1999
Текст
' Высшая математика
В.И.Нечаев
ЭЛЕМЕНТЫ
КРИПТОГРАФИИ
ОСНОВЫ ТЕОРИИ
ЗАЩИТЫ
ИНФОРМАЦИИ•
ВЫСШАЯ ШКОЛА
irf' V. 1 .. л
<• ; ' i i
*»
Учебное издание
Нечаев Василии Ильич
ЭЛЕМЕНТЫ КРИПТОГРАФИИ
(Основы теории защиты информации)
Редакторы Л.Л. Степанова, Ж. И. Яковлева
Художественный редактор Ю Э. Иванова
Технические редакторы Л В Шитова, Л.А- Овчинникова
Компьютерная верстка Л.В Шитова
ЛР N" 010146 от 25.12.96. Изд № ФМ-199. Сдано в набор 08 04 99.
Подписано в печать 19.04 99 Формат 60х88!/|б Бум офс № 1
Гарнитура «Таймс» Печать офсетная. Объем 6,86 усл. печ. л.
7,37 усл. кр.-отт 4.76 уч.-изд. л.
Тираж 8000 экз. Зак. №364
Издательство «Высшая школа», 101430. Москва. ГСП-4, Нсглинная ул., д. 29/14.
Отпечатано в ОАО «Оригинхт», 101898, Москва, Центр, Хохловский пер., д. 7.
ИЗДАТЕЛЬСТВО
«ВЫСШАЯ
ШКОЛА»
Выпускает базовые учебники, учебные, методические и учебно-
наглядные пособия (плакаты), справочники, научные издания для
студентов вузов, техникумов, колледжей, учащихся лицеев, школ,
абитуриентов, а также для широкого круга читателей.
Любая форма расчетов - гибкая
система скидок; официальным
дилерам - гарантированные
скидки.
Резервирование литературы - по
предварительным заказам, при
условии гарантированной
оплаты.
Доставка - самовывоз, пересылка
"книга-почтой", железнодорожным
транспортом, бесплатная перевозка
по Москве при покупке литературы
на сумму свыше 10 тыс. руб.
Заказать и приобрести книги Вы можете непосредственно в
издательстве, библиотечных коллекторах, облкнигах, магазинах и
книготоргующих организациях, расположенных в крупных городах.
России и СНГ.
УДК 511
ББК 22.13
Н 59
Рецензенты
кафедра теории чисел механико-математического факультета МГУ
им. М.В Ломоносова (зав. кафедрой проф. А.Б Шидловский);
проф А. И. Павлов (МИАН им В.А Стеклова)
Нечаев В.И.
Н 59 Элементы криптографии (Основы теории защиты информации):
Учеб пособие для ун-тов и пед. вузов / Под ред. В. А Садовничего -
М : Высш, шк., 1999. - 109 с.
ISBN 5-06-003644-8
Книга является первым учебным пособием по теории защиты информа-
ции. фундаментом ко горой является прикладная теория чисел. В ее основу по-
ложены лекции, читавшиеся автором на математическом факультете Москов-
ского педагогического государственного университета
В книге рассматриваются современные методы шифрования по открытому
ключу и электронная подпись.
Книга отличается широтой охвата материала в области защиты информа-
ции. В ней также содержится интересный исторический очерк развития крип-
тографии
Для студентов университетов, педагогических вузов и вузов с углублен-
ным изучением математики. Будет полезна широкому кругу читателей, начи-
ная с учащихся старших классов математических школ.
ISBN 5-06-003644-8
БИБЛИОТЕКА!
Калининградского
государственного
университета
© Издательство "Высшая школа", 1999
Оригинал-макет данного издания является собст-
венностью издательства 11 Высшая школа” и его ре-
продуцировагше (воспроизведение) любым спосо-
бом без согласия издательства запрещено
Василий Ильич Нечаев родился в Москве в 1920 г Его интерес к математи-
ке и математический талант были очевидны еще в школе Школьные годы стали для
него также временем активного самообразования В 1937 г он поступает на физико-
математический факультет Московского городского- педагогического института и
оканчивает его с отличием в июне 1941 г.
15 октября 1941 г., в трагические дни немецкого наступления на Москву
В.И Нечаев добровольцем ушел в Красную Армию. Участвовал в сражениях на За-
падном и Сталинградском фронтах в составе 241-го Гвардейского Особого разведы-
вательного батальона, прошел с боями всю войну, дважды был тяжело pai юн. Войну
закончил младшим лейтенантом. За боевые заслуги насажден орденом Красного
Знамени, орденом Отечественной войны П степени и многочисленными медалями.
После войны В.И Нечаев приступает к активной наугной работе, и вся его по-
следующая деятельность связана с МГТП1 им. В И. Ленина и Математическим инсти-
тутом им В.А. Стеклова. Демобилизовавшись из армии, он возвращается в институт
и учится в аспирантуре под руководством профессора М.К. Гребенчи. По окончании
аспирантуры в 1949 г. по рекомендации академика И М Виноградова становится за-
ведующим кафедрой алгебры и элементарной математики Московского городского
педагогического института. С 1963 г - старший, а затем - ведущий научный сотруд-
ник МИАН СССР (позднее РАН). Одновременно продолжает педагогическую дея-
тельность в МП1И С 1978 г. и до конца жизни руководит кафедрой теории чисел
МПГУ. С 1948 г. - кандидат физико-математических наук, с 1975 г. - доктор физико-
математических наук, профессор.
3
В, И Нечаеву принадлежат важные результаты в области аналитической тео-
рии чисел: новые верхние и нижние оценки в проблеме Варинга для специальных
целозначных многочленов
х - (х + 1) ... (х + п — 1)
и! ’
правильные по порядку оценки сверху полных рациональных тригонометрических
сумм; оценки полных лригонометрических сумм и сумм с характерами с рекуррент-
ными функциями ВИ Нечаев получил также ряд значительных результатов в тео-
рии линейно-рекуррентных последовательностей над конечными полями. Его идеи
оказали сущее тленное влияние на развитие этой ветви прикладной математики. На-
учные труды В.И. Нечаева хорошо известны как в нашей стране, так и за рубежом. За
работу в области прикладной математики он награжден орденом "Знак Почета"
В.И. Нечаев был одним из крупнейших специалистов по вопросам педагоги-
ческого образования, автором учебных программ по алгебре, теории чисел, числовым
системам, элементарной математике, прикладным вопросам теории чисел; автором
нескольких учебников, многочисленных статей в Математической, Детской, Школь-
ной математической энциклопедиях. Награжден знаком "Отличник народного про-
свещения1’ и Золотой медалью ВДНХ.
В.И Нечаев придавал огромное значение научном}' прсемничеству, воспита-
нию и поддержке талантливой молодежи. Его многочисленные ученики. в разных
городах и странах мира, продолжают его дело. Те, кому довелось знать Василия Иль-
ича Нечаева или учиться у него, всегда будут с восхищением и благодарностью вспо-
минать не только блеск его интеллекта, эрудицию, широту культурных интересов и
интеллектуальную независимость, но и его высокие душевные качества, непоколеби-
мое благородство, сочетавшееся с терпимостью и вниманием к людям.
На протяжении многих лет профессор В.И. Нечаев являлся членом редколле-
гии журнала "Математические заметки", членом Совета математического факультета
МИГУ, членом специализированного Совета по присуждению ученых степеней и
членом секции алгебры и теорйи чисел научно-методического Совета по математике
и вычислительной технике УМО на базе МПГУ
В И Нечаев много лет работал в области прикладной математики. Он был
одним из инициаторов включения этого предмета в учебную программу математиче-
ского факультета МПГУ. Цикл лекций, прочитанный им по прикладным вопросам
теории чисел - элементам криптографии - лег в основу настоящего пособия Будучи
тяжело болен, он до последних дней жизни продолжал работать над этой книгой.
ПРЕДИСЛОВИЕ РЕДАКТОРА
В России исторически сложилось так, что представление об образова-
нии включает в себя органичное единство школы как системы приобретения
знаний, фундаментальной науки как показателя уровня подготовки специали-
стов и гуманитарной культуры как основы духовного богатства человека
Формулируя задачи образования, академик А Н Крылов говорил:
"Школа нс может дать вполне законченного знания, главная задача школы -
дать общее развитие, дать необходимые навыки, одним словом, главная за-
дача школы - научить учиться, и для того, кто в школе научится учиться,
практическая деятельность всю его жизнь будет наилучшей школой."
Отмстим, что особенность отечественной школы состоит в сочетании
четкости рассуждений с глубиной содержания и простотой, доступностью,
конкретностью изложения материала, которые всегда предпочитаются фор-
мальным конструкциям. Практическое воплощение данных идей подразу-
мевает наличие высококвалифицированных и творчески мыслящих препо-
давателей.
Математическое образование и математическая культура составляют
стержень научного знания и значение математики как основы фундаменталь-
ных исследований постоянно возрастает.
Для решения этих задач требуются учебники, отражающие в опреде-
ленной полноте современное состояние исследований и мировоззренческие
принципы данной области науки
Предлагаемые к публикации избранные учебники по математике реа-
лизуют указанный выше подход. Они написаны, в основном, профессорами
Московского государственного университета им М.В. Ломоносова
Книга В.И. Нечаева "Элементы криптографии (Основы теории защиты
информации)" является первым учебным пособием по теории защиты инфор-
мации, фундаментом которой является прикладная теория чисел. В основу
книги положены лекции, читавшиеся автором в течение последних лет на ма-
гсматическом факультете Московского педагогического государственного
университета. В пособии рассматриваются современные методы шифрования
но открытому ключу и электронная подпись. Книга отличается широтой охва-
та материала в области защиты информации. В ней также содержится инте-
ресный исторический очерк развития криптографии Она доступна широкому
кругу читателей, начиная с учащихся старших классов математических школ.
В данной серии утке изданы учебники и учебные пособия: Архи-
пов Г. И., Садовничий В.А., Чубариков В.Н. Лекции по математическому ана-
лизу, Виноградов ИМ Элементы высшей математики. (Аналитическая гео-
метрия. Дифференциальное исчисление. Основы теории чисел), Прива-
лов ИИ. Введение в теорию функций комплексного переменного, Садовни-
чий В. А. Теория операторов, Гашков С.Б., Чубариков В.Н. Арифметика. Ал-
горитмы Сложность вычислений.
5
Надеюсь, что данные книги положат начало новой серии базовых
учебников по высшей математике для вузов с повышенным уровнем матема-
тической подготовки
Кроме практической ценности эта серия призвана подвести некоторые
итоги работы российских ученых и педагогов-математиков по созданию базо-
вых учебников по математике на рубеже второго и третьего тысячелетий Се-
рия нс ограничивается указанными книгами В дальнейшем предполагается
продолжить отбор и издание как современных, так и классических учебников,
которые отвечают изложенной выше концепции, нс потеряли своей новизны и
актуальности и пользуются заслуженной популярностью и авторитетом у сту-
дентов и педагогов
Академик Российской академии наук В. А. Садовничий
ПРЕДИСЛОВИЕ
Элементы криптографии
В последней трети XX в. исключительно важное значение в разных
областях математики приобрели вопросы, связанные с сохранением и переда-
чей информации. Возникающие при этом задачи решает криптография - нау-
ка о методах преобразования информации в целях се защиты от незаконных
пользователей. Большой вклад в развитие современных методов криптогра-
фии принадлежит теории чисел.
Возникновение криптографии теряется в глубине тысячелетий. Ее не-
обходимость возникла в связи с конкуренцией человеческих сообществ.
Первая часть книги содержит краткие сведения о различных приемах
шифрования: квадрат Полибия, шифр Цезаря, шифр Тритемиуса, решетка
Кардано, маршрутная и постолбцовая транспозиции, квадрат Вижснсра, пе-
ремешанные алфавиты, одноразовый шифровальный блокнот, шифр "по кни-
ге", тюремный шифр, парный шифр, шифр "по стихотворению"
Вторая часть книги знакомит с современными методами шифрования;
открытый ключ, электронная подпись
Третья часть книги включает необходимые сведения из теории конеч-
ных полей. Она включает также следующие вопросы: дискретный логарифм,
экспоненциальный открытый ключ, оценка сложности детерминированных
алгоритмов вычисления дискретного логарифма, конструкция псевдослучай-
ной последовательности на основе ненулевого решения линейного рекуррент-
ного уравнения, локация удаленных и быстродвижущихся объектов, псевдо-
случайные последовательности и криптография
Выражаю глубокую признательность Л.Л. Степановой и Л.В Шитовой,
которые оказывали автору существенную помощь при написании книги, а
также всем, кто в той или иной мерс способствовал изданию этого труда.
Автор
ОБОЗНАЧЕНИЯ
/V, /Vo, Р, Z, Q, R, С множества натуральных, неотрицательных целых, простых, целых, рациональных, действительных и комплексных чисел соответственно;
Р — простое число.
1 — отношение делимости {а b -а делит А),
(«, Л) — наибольший общий делитель целых чисел а и А;
|«, А] — наименьшее общее кратное целых чисел а и Ь;
[а) — целая часть действительного числа а, т е. наибольшее целое, не превосходящее а. Таким образом, |а] а < [а] + 1;
•••, q *1 — цепная дробь с элементами qoe Z, q i е N, i > 1;
Ф («) — функция Эйлера;
ц(«) — функция Мебиуса;
п * а — натуральное кратное;
= •— отношение сравнимости (а = b (mod m) - а сравнимо с А по модулю ш);
— класс вычетов по модулю т с представителем а, то есть множество целых чисел, сравнимых с а по модулю т;
Z /(т) — кольцо классов вычетов по модулю т;
FM кольцо многочленов от неизвестного х над полем F;
4л — фактор-кольцо кольца F[x] по идеалу (/), если
f - многочлен над полем F.
8
Глава 1. ИЗ ИСТОРИИ
КРИПТОГРАФИИ
§1. Криптография
Криптография - тайнопись. Термин ввел Д. Валлис. Потребность
шифровать и передавать шифрованные сообщения возникла очень давно
Так, еще в V-IV вв до н. э. греки применяли специальное шифрующее уст-
ройство. По описанию Плутарха, оно состояло из двух палок одинаковой
длины и толщины. Одну оставляли себе, а другую отдавали отъезжающему.
Эти палки называли скиталами Когда правителям нужно было сообщить
какую-нибудь важную тайну, они вырезали длинную и узкую, вроде ремня, поло-
су папируса, наматывали ее на свою скигалу, нс оставляя на ней никакого проме-
жутка, так чтобы вся поверхность палки была охвачена этой полосой. Затем, ос-
тавляя папирус на скиталс в том виде, как он есть, писали на нем все, что нужно,
а написав, снимали полосу и без палки отправляли адресату. Так как бук-
вы на ней разбросаны в беспорядке, то прочитать написанное он мог, только
взяв свою скиталу и намотав на нес без пропусков эту' полосу.
Аристотелю принадлежит способ дешифрования этого шифра.
Надо изготовить длинный конус и, начиная с основания, обертывать его
лентой с шифрованным сообщением, постепенно сдвигая ее к вершине В
какой-то момент начнут просматриваться куски сообщения. Так можно
определить диаметр скиталы.
В Древней Греции (П в. до н. э.) был известен
шифр, называемый "квадрат Полибия". Это уст-
ройство представляло собой квадрат 5x5, столб-
цы и строки которого нумеровали цифрами от 1
до 5. В каждую клетку’ этого квадрата записыва-
лась одна буква. (В греческом варианте одна клет-
ка оставалась пустой, в латинском - в одну клетку
помещали две буквы i и j.) В результате каждой
букве отвечала пара чисел и шифрованное сообщение
превращалось в последовательность пар чисел Например,
13 34 22 24 44 34 15 42i
Это сообщение записано при использовании латинского варианта
"квадрата Полибия", в котором буквы расположены в алфавитном порядке
9
А В С D Е
F G Н I, J К
L М N О Р
Q R S Т U
V W X Y Z
В I в. н.j. Ю. Цезарь во время войны с галлами, переписываясь со
своими друзьями в Риме, заменял в сообщении первую букву латинского
а правша (А) на четвертую (D), вторую (В) - на пятую (Е), наконец, по-
с юдиюю - на третью:
(ABCDEFGHI JKLMNOPQRSTUVWXYZ
DEFGH I JKLMNOPQRSTUVWXYZABC
Сообщение об одержанной им победе выглядело так.
YHQL YLGL Y L F 1?’
Император Август (I в. н. э.) в своей переписке заменял первую бук-
ву на вторую, вторую - на третью и т. д., наконец, последнюю - на первую:
(ABCDEFGH I JKLMNOPQRSTUVWXYZ
BCDEFGH I JKLMNOPQRSTUVWXYZA
Его любимое изречение было.
"GFT U J О В М F О U F"31
а..............................—................................................И
Квадрат Полибия, шифр Цезаря входят в класс шифров, называемых
"подстановка" или "простая замена". Это такой шифр, в котором каждой
букве алфавита соответствует буква, цифра, символ или какая-нибудь их
комбинация.
В известных рассказах "Пляшущие человечки" Конан Дойля и
"Золотой жук" Эдгара По используемые шифры относятся к указанному
классу шифров В другом классе шифров -"перестановка" - буквы сооб-
щения каким-нибудь способом переставляются между собой. К этому классу
принадлежит шифр скитала.
К классу "перестановка" относится шифр "маршрутная транспо-
зиция" и его вариант "постолбцовая транспозиция". В каждом из них в
данный прямоугольник (л х т\ сообщение вписывается заранее обусловлен-
ным способом, а столбцы нумеруются или обычным порядком следования, или в
порядке следования букв ключа - буквенного ключевого слова Так, ниже в пер-
вом прямоугольнике столбцы нумеруются в обычном порядке следования - слева
направо, а во втором - в порядке следования букв слова "Петербург".
Используя расположение букв этого ключа в алфавите, получим набор
чисел [53 846 1 9 7 2]:
1 2 = 3 4 i 5 6 7 8 9 5 3 8 4 6 1 9 7 2
п р ? и л i е п л я я п р и л е п л я я
р Д j У м i е Р п я с" с~ я п Р е м У Д Р
У м п р ; е м У Д р У Р У Д Р
в ГС ю ь : ш е Д У б б У Д е ш ь а б в
10
В первом случае шифрованный текст найдем, если будем выписывать
буквы очередного столбца в порядке следования столбцов (прямом или об-
ратном). во втором, - если будем выписывать буквы столбца в порядке сле-
дования букв ключа. Таким образом, будем иметь:
1) прувр дмбиу палмр ьеееш прмел пудяя дуяерб;
2) пммья ррвря мулрр епсуб ееешя ддбип пдлууа;
ilh поачания Даниила Заточенаго к великому князю Ярославу Всевачодичю)
К классу "перестановка" принадлежит и шифр, называемый "ре-
шетка Кардано". Эго прямоугольная карточка с отверстиями, чаще всего
квадратная, которая при наложении на лист бумаги оставляет открытыми
лишь некоторые его части. Число строк и столбцов в карточке четно Карточ-
ка сделана так, что при ее последовательном использовании (поворачивании)
каждая клетка лежащего под ней листа окажется занятой. Карточку' сначала
поворачиваю! вдоль вертикальной оси симметрии на 180°, а затем вдоль го-
ризонтальной оси также на 180° И вновь повторяют ту же процедуру:
Если решетка Кардано - квадрат, то возможен второй вариант самосо-
вмещенин фигуры, а именно, последовательные повороты вокруг центра
квадрата на 90°:
Рассмотрим примеры:
11
Легко прочесть зашифрованное квадратной решеткой Кардано сооб-
щение:
"вавоче муноти мыжрое ьухсой мдосто яаентв" )
Второе сообщение:
"ачшдеалб еымтяовн лыриелбм
оянгеаюш дтинрент еоеыпрни"5)
также нетрудно расшифровать, пользуясь прямоугольной решеткой.
Термин ’’шифр" арабского происхождения В начале XV в. арабы
опубликовали энциклопедию "Шауба Алъ-Аща", в которой есть специаль-
ный раздел о шифрах. В этой энциклопедии указан способ раскрытия шифра
простой замены. Он основан на различной частоте повторяемости букв в тек-
сте. В этом разделе есть перечень булев в порядке их повторяемости на основе
изучения текста Корана Заметим, что в русском тексте чаще всего встречает-
ся буква “О", затем буква "Е" и на третьем месте стоят буквы "И" и "А”. Более
точно: на 1000 букв русского текста в среднем приходится 90 букв "О", 72 буквы
"Е" или "Ё" и по 60 букв "И” и "А" и т.д
Неудобство шифров типа "подстановка" ("простая замена") в случае
использования стандартного алфавита очевидно. Таблица частот встречаемо-
сти букв алфавита позволяет определить один или несколько символов, а это-
го иногда достаточно для дешифрования всего сообщения ("Пляшущие че-
ловечки" Конан Дойля или "Золотой жук" Эдгара По). Поэтому1 обычно
пользуются разными приемами, чтобы затруднить дешифрование. Для
этой цели используют многобуквенную систему шифрования - систему,
в которой одному символу отвечает одна или несколько комбинаций двух и
более символов. Другой прием - использование нескольких алфавитов.
В этом случае для каждого символа употребляют тот или иной алфавит в
зависимости от ключа, который связан каким-нибудь способом с самим сим-
волом или с его порядком в передаваемом сообщении.
В процессе шифрования (и дешифрования) используется таблица
("таблица Виженера"), которая устроена следующим образом: в первой
строке выписывается весь алфавит, в каждой следующей осуществляется
циклический сдвиг на одну букву. Так получается квадратная таблица,
число строк которой равно числу столбцов и равно числу букв в алфави-
те. Ниже представлена таблица, составленная из 31 буквы русского ал-
фавита (без букв Ё и Ъ). Чтобы зашифровать какое-нибудь сообщение,
поступают следующим образом. Выбирается слово - лозунг (например,
"монастырь") и подписывается с повторением над буквами сообщения
Чтобы получить шифрованный текст, находят очередной знак лозунга,
на1гиная с первого в вертикальном алфавите, а ему соответствующий знак со-
общения в горизонтальном. В данном примере сначала находим столбец, от-
12
всчающий букве "м" лозунга, а затем строку, соответствующую букве "р" от-
крытого текста. На пересечении выделенных столбца и строки находим бук-
ву "э". Так продолжая дальше, находим шифрованный текст полностью:
м о н а с т ы Р ь м о н а с т ы р ь м о н
р а с к и н У л о с ь м о Р е ш и р о к о
э о я к Щ a л ы й ю й щ о в ч ф ш л ь ш ы
Таблица Виженера
i - . »; i 1
А; Б : В: Г : Д: Е : Ж; 3
Б : В’: Г: Д: Е: Ж: 3: И
* « *<ф** 4*{*4 4 4^4Ъ4 * {4 4 4.4^ 4 4 44^4 44 4 ф. О • 4.
Г [-- | Т-- I !-" т- '7 Т !, , ..г— у, —|
и; И: К: Л: М: Н: О: П: Р : С: Т: У: Ф: X! II: Ч: НЕ НЕ Ь : Ы: Э: КЗ Я
•«>••••{......}.—* <**..*).*.-4.....................................................................
?i.K.
.fl!
хГЯЗЫМкИм
. ж1.з 1 й] й i к i л: 1 кЁ н
"д! _Й. .9..
иТйГ кГл I м:: Hi bl п
й: к: Л: Mi Н: О': П: Р
..*}*•*..
.АЦ.Я1М.Н:..О1.П.:.Р^.С,
.я1.И.н[о: nj pj cJ t
Mi Hi oi nl p i cl т1 у
Л i Mi Н: О i П i Р i С i Т i У i ф; Xi Ц; Ч i Щ Щ: Ь ; LI: Э ; Ki Я : А Б i в
*444«4«44 4^ 444 4 «4 «4* 4(4*44* ф* 4 4 4 *4**4 4 4 4 4*4 4 • 4 4* 4 4 4 4444 *«** 4 о 4* •♦*•* 4 *•• *• *4* ** 4 4 4 4 **** 44*4*44 4* 4*4 4 *44444*4*44 *4 44*4*44441
С : Т i У: ф: X: 11; Ч : Щ IIE Ь : Ы: Э: КЗ Я : А: Б В : Г : Д: Е : Ж[ 3 : И
Я i.AiIХ1 -Д.:.Ж.1-?К!.3.:.И1 Й.х.К,
Ф: хТ ill Ч : ш[ Щ- Ь i ы1’э! id ЯрА: Б I в1г i д! Е : ж[ 3 I Hi ЙТ к[Л
4 4* 4 в *.***1 4 * 4 4 •* *.*4 *4 *444 4 44*4*4*4 4 4*4 44 444 4444***4 • * 4 4 4**4 • *• 4**«*44**4 4 * « 1*4 ****** ****** **4*4**«***. 4*4*4 *4*4*444*4
П: Р : С
О: П: P? C= ri У: ф: X
LLE JLLE Ь = Ы= 3 i КЗ Я '
......................)4 4.4{..4 44«4.44'
1Д Ь i Ы; Э : КЗ Я : А
4444,4.4 4 ^444 4 f444 4 4>44 4 4 {* 4 * * 4 } * 4 4 *
Р : С: T: У: Ф: X: Ц: Ч
С: Т: У: Ф: X: Ц: Ч: Н
4 44 4«}**.4 {4444 4}4 4 «*{« 4 4 4 4}4 4 44 {«4 4 4 ф .» * * 4
Т: У: ф: X: П: Ч: ВЦ 11^ Ь ; Ы: Э i КЗ Я: А: Б
4 44 4} 4 4 44{4 4 4 44 44 4 { О О * 4*} * 4 4 * ф 4*4 4 4.4^4..4 * 4 44 в .444^444*4^44 Я В ^4 4444 £ 4*4*
я.’..а; бJ в
oi kJя1 Ai б’Тв1 г
П: P[Cj Т
еТзТи": йIк! л 1 м[н^ о!п! Р j сТтI V
4 4 4*4 4 4*444 4.ф 44*444*4 • 4 • .4 «4 » 4* 44 4 4 4 • **4 4* *4 4 4 4 4 4 44 4*4*а*4444«4444 * •••• 4 • 44*4 I
^.3.1.У1.й[к£л] Mi н=о: п; pJ.c.: т£у:.ф
ж зТи= й"кi л! м= нi оТ пi р i с i т1 уi ф= х
Г
Я: Б : В . ГД.:.Е
ч i ni ni ь i ы; э = кз я
« 4 4 4^4*4 » /* 4*4^44 4 4 4^*4 4 4 *J> 4*4 4 Г* 4 4 4 ф 4 4*4
не ш ы bii Э; кзя: а
...с............>•—<—>
АХХШ.Я А-Б • В j Г
эТ шГяГа1 б! в1 гТд
Г 4 *4* ***** • ***** * * «••* ***••***« * 4**44 * * 44
б • в: ri ai E: ж: з
--
В: Г: Д: E: Ж: 3: И
--ХЛ(.....».•••
Llfli.E i.2£.3.1 И.Й
.AixIMxLhllliiX
е : жТз I и; й; K‘i л
Й! К: Л: М.= Н=. О: П: Pi С: Т = У: Ф: X: 11: Ч
.................................................ГЛ [.........
Я: А: Б: В; Г: Д: Е] Ж
ж: 3 i И? Й] к= Л i Mi н
Н: О; П? Р S С? Т: У: Ф;: X] II: Ч : Щ 1Ц[ Ь ’• Ы
44* *4> *»**>*«** ' W 0444 4*4 4 4 4 ****** 4* •* 4 4 *44 4 4 44444 ... 4444444444444* -^4 44 44#444 44
ni рi с' тi у\ ф; xi ц; ч; щ щ ь : bii э|ю
3 ! И: Й i К: Л: Mi H
Наконец, к сообщению можно применять несколько систем шифрования.
Аббат Тритемиус - автор первой печатной книги о тайнописи
(1518 г.)- предложил несколько шифров и среди них шифр, который можно
считать усовершенствованием шифра Цезаря. Этот шифр устроен так Все
буквы алфавита нумеруют по порядку (от 1 до 33 в русском варианте). Затем
выбирают какое-нибудь слово, называемое "ключом", например "Вологда",
и подписывают под сообщением с повторением, как показано ниже:
13
бопера циянач инаетсяввоск р е се н ь е =
вологдавологдавологдавологдаво:
Чтобы получить шифрованный текст, складывают номер очередной
буквы с номером соответствующей буквы ключа. Если полученная сумма
больше 33, то из нес вычитают 33. В результате получают последователь-
ность чисел от 1 до 33. Вновь заменяя числа этой последовательности соот-
ветствующими буквами, получают шифрованный текст. Разбивая этот текст
на группы одной длины (например, по 5), получают шифрованное сообщение.
[ " С ЯС АД ЫЙ В Э М ЖМ ТБ 3 В ЮО ЁЖ ПIФ Ъ 3 ФГ XЙIOi Я Ф "
Если под ключом шифра понимать однобуквенное слово "В" (в рус-
ском варианте), то мы получим шифр Цезаря В этом случае для того же тек-
ста шифрованное сообщение принимает вид
"СТЗУГ ЩЛВРГ ЪЛРГЗ ХФВЕЕ СФНУЗ ФЗРЯЗ”
Появившийся в XVIII в. шифр "по книге" можно рассматривать как
дальнейшее усовершенствование шифра Ю. Цезаря. Чтобы воспользоваться
этим шифром, два корреспондента договариваются об определенной книге,
имеющейся у каждого из них. Например, Гашек Я. Похождения бравого
солдата Швейка. М., 1977. В качестве ключа каждый из них может вы-
брать "слово" той же длины, что и передаваемое сообщение Этот ключ
кодируется парой чисел, а именно номером страницы и номером строки
на ней, и передается вместе с шифрованным сообщением. Например,
(287,2) определяет "слово", т. е. текст избранной книги: "Внимательно
прочитав эту страницу, офицеры ничего не поняли..." Этому ключу
отвечает последовательность чисел:
; 03 15 10 14 01 20 06 13 30 15 16 17 18 16 25 10 20 01 03 31 20”2119 20 1815 10 24 21Т 1
Зная этот ключ, можно легко расшифровать сообщение:
Г/?9Нюп“ ечхвш............рхщющ........хушрм....................]
(Заметим, что в названной книге на указанной странице описывается вариант
шифра "по книге".)
Примером нераскрываемого шифра * может служить "одноразовый
шифровальный блокнот" — шифр, в основе которого лежит та же идея, что
и в шифре Цезаря. Назовем расширенным алфавитом совокупность букв
алфавита, знаков препинания {.,:;?!()-”} и знака пробела между' словами.
Число символов расширенного алфавита в русском варианте равно 44. Занумеру-
ем символы расширенного алфавита «телами от 0 до 43. Тогда любой персдавас-
14
мый текст можно рассматривать как последовательность {«„} чисел множества
,4 = {0,1,2,43}.
Предположим, что имеем случайную последовательность {с„} из
чисел множества А той же длины, что и передаваемый текст (ключ). Складывая
по модулю 44 число ап передаваемого текста с соответствующим числом с„
ключа
а„+с„ = Z>„(mod 44), 0 Ьп <, 43,
получим последовательность {Ь„} знаков шифрованного текста. Чтобы по-
учить передаваемый текст, можно воспользоваться тем же ключом
ап = h„- c„(mod 44), 0 < а„ £ 43.
У двух абонентов, находящихся в секретной переписке, имеются два
одинаковых блокнота В каждом из них на нескольких листах напечатана
с ^ чайная последовательность чисел множества А. Отправитель свой текст
шифрует указанным выше способом при помощи первой страницы блокнота.
Зашифровав сообщение, он уничтожает использованную страницу и отправ-
1яет его второму абоненту; получатель шифрованного текста расшифровы-
вает его и также уничтожает использованный лист блокнота. Нетрудно
видеть, что одноразовый шифр нераскрываем в принципе, так как символ
в тексте может быть заменен любым другим символом и этот выбор со-
вершенно случаен.
Случайная последовательность чисел множества А может быть по-
лучена при помощи "вертушки со стрелкой" (рис. 1). Обод вертушки
разделен на 44 равные части (дуги). Каждая из них помечена числами от
О до 43. Запуская вертушку, по-
лучим какое-нибудь из чисел
множества А. Так продолжая
дальше, можем получить случай-
ную последовательность любой
длины.
С появлением радио- и те-
леграфных линий всякую инфор-
мацию удобно передавать, ис-
пользуя двоичный код, напри-
мер азбуку Морзе. В современ-
ных системах шифрования обычно
шифруют сообщения, записанные
двоичным кодом. Далее будет
рассмотрена система шифрования
двоичной последовательности, в которой идея шифра Цезаря получает
дальнейшее развитие.
15
§2. Тайнопись в России
Первое известное применение тайнописи в России относится к XIII в.
Эту систему называли "тарабарской грамотой". В этой системе согласные
буквы заменяются по схеме:
♦ бвгджзклмн
{щшчцхфтсрп
(при шифровании буквы, расположенные на одной вертикали, переходят одна
в другую), остальные буквы остаются без изменения. Так, известная послови-
ца, записанная этим шифром, выглядит так:
ычпиек7)
Образцом алфавита, придуманного во второй половине XVII в. специ-
ально для передачи секретных сообщений, может служить тайнопись
"уголки " и ключ к ней. Эта тайнопись состоит в замене обычных букв уголь-
никами и четырехугольниками, заимствованными из решетки, составленной
из двух параллельных линий, пересеченных двумя такими же линиями под
прямым углом. В полученных клетках размещены по четыре и три буквы в
порядке следования букв алфавита. В тайнописи буквы заменяются, при этом
первая - простым угольником, а следующие - тем же угольником с одной,
двумя или тремя точками, смотря по месту буквы в нем.
Ключ к шифру "уголки"
16
В эпоху Петра I в качестве системы шифрования широко употреблялась
"цифирь" или "цифирная азбука". Цифирь - это шифр простой замены, в ко-
|кром буквам сообщения соответствовали ишфрообозначения, представляющие
। обой буквы, слоги, слова или какие-нибудь другие знаки. При этом использо-
к.1 inch и "пустышки" - шифрообозначения, которым нс соответствовали
никакие знаки открытого текста, т. е передаваемого сообщения. В госархиве
«охр.шились письма Петра, в которых он передавал цифири различным деятелям
I i»i корреспонденций (П.А. Толстому, А.Д. Меньшикову,...).
В эпоху царствования Елизаветы Петровны обычным делом была пср-
in hi рация переписки иностранных дипломатов. Результаты этой "работы" нс-
|‘олько раз в месяц докладывались царице. Некоторое время "специалисты" по
in р иострации пропускали те места корреспонденций, смысл которых им был ис-
пошлен В 1742 г. канцлер Алексей Петрович Бестужев-Рюмин пригласил на
। ну жбу в коллегию иностранных дел математика, академика Петербургской АН
\ристиана Гольдбаха. С этого времени псрлюстраторам было дано распоряже-
ние । щательно копировать письма, не опуская при этом кажущихся им мелочей. В
р> iv льготе только за июль-декабрь 1743 г. X. Гольдбах смог дешифровать
г»1 письмо министров прусского и французского дворов. В тоге переписка ино-
t1 ранных послов в конце XVH1 в. перестала быть тайной для дешифровальной
। цжоы России. За свою успешную работу Гольдбах был пожалован в тайные советни-
цы ежегодным окладом в 4500 руб.
Шифры подполья
а) Тюремная азбука - аналог квадрата Полибия.
Она позволяла путем перестукивания сообщаться заключенным разных
। ,|мср Эта азбука устроена так. в прямоугольник 6x5 вписываются буквы
русского алфавита в обычном порядке следования, кроме букв ё, й, ъ. В ре-
ши мате получается таблица:
1 2 3 4 5 Каждая из основных
1 ? а б в г Д букв русского алфавита (без
2 е ж 3 и к букв ё, й. ъ) определяется па-
л i л м н о п рой чисел - номером строки и
4 !₽ в X с Ц т ч У ш ф Щ столбца. Поэтому вопрос: "Кто здесь?" изображается следую- щим образом:
0 ь ы 3 ю я
в • •• в • ••• •• • вв в в в 1» в ВВ
б) Парный шифр, ключом которого является фраза, содержащая 15
разных букв. Подписывая под этими буквами буквы в алфавитном порядке,
th вошедшие в этот ключ, получаем разбиение 30 основных букв русского
,|||ф.пцпа на пары. Чтобы получить из сообщения шифрованный текст, заменя-
17
ют каждую букву сообщения своим напарником. Так, выбирая в качестве ключа
фразу "железный шпиц дома лежит", получим разбиение основных букв рус]
ского алфавита на пары, как указано ниже:
П 2 3 ’’ 4"”б" 6 7 8 9r i dГ 11 — 15 }
'ЖЕЛЕЗНЫЙШПИЦ Д о М А ЛЕЖИ Т =
[Б В Г К P C У Ф X ч щ ь э ю Я
Таким образом, получаем отображение букв основного алфавита на
последовательность, состоящую из тех же букв:
а б в г д е ж з икл мноп рст у фх ц ч шщь ыэ ю я ]
,„[юж е л щв б к х з г эр ь фн ы я ш п и ч ц у д ос мат]
Поэтому сообщение "Ветрена отменяется, явка раскрыта", пере-
ходит в следующий шифротскст:
ЕЫЯНВ ЦЮЬЯЭ ВРТВЯ ЫТТЕЗ ЮНЮЫЗ НСЯЮ
Очевидно, что в качестве ключа можно также использовать любую
фразу, в которой имеется не менее 15 разных букв основного алфавита.
Пример 1:
1 2 3 4 6 6 7 8 9 10 11 12 13 14 16
ИМОСКВАНЕСР АЗ У СТ РОИЛ АСЬ
А'..................................................:
\АБВГДЕЖЗИКЛ МН О ПР С Т У Ф X Ц Ч Ш Щ Ь 3 Ю Я:
,,:ХИФБВЧСЩБПЮ ГЦ Д К Ш Ж 3 Ы В АНЕ Р 3 Я Т Л Ь\
ч........................ -.............. ...*
Пример 2:
1 2 3 4 6 6 7 8 9 10 11 12 13 14 15
УКРИВОЙНАТАЛ Ь ИВС Е ЛЮД ИКАНАЛЬИ
БГЖЗМП ФХЦ Ч Ш Щ Ы ЭЯ
t] А Б В Г Д Е Ж 3 И К Л М Н ОПР С ТУ Ф ХЦЧШЩЬЫЭЮЯ
, r 1 X У м И Я Ы Р И 3 Г Ч В Ф П О Ж Щ ЦБ Н АТЛЬСШЕЮЭД
Вопрос. Пользуясь ключами примеров 1 и 2, получить новые
шифротекегы сообщения ’’Встреча отменяется, явка раскрыта”.
в) По стихотворению - вариант шифра "по книге".
Корреспонденты договариваются о достаточно объемном стихотвор-
ном произведении, которое заучивают наизусть. Например, роман "Евгений
Онегин" или поэма "Кому на Руси жить хорошо". Каждую букву сообще-
ния шифруют парой чисел - номером строки, где встречается эта буква, и
номером буквы в ней.
Пусть выбрана поэма "Кому на Руси жить хорошо”. Пролог поэмы на-
чинается строфой:
18
1 В каком году - рассчитывай, 9 Из смежных деревень:
2 В какой земле -угадывай, 10 Заплатова, Дырявина,
3 Па столбовой дороженьке 11 Разутова, Знобишина,
4 Сошлись семь мужиков: 12 Горелова, Неелова —
5 Семь временнообязанных, 13 Пеурожайка тож,
6 Подтянутой губернии 14 Сошли ся и заспорили:
7 Уезда Терпигорева, 15 Кому живется весело,
8 Пустопорожней волости, 16 Вольготно на Руси?
Для удобства шифрования текст (выбранного стихотворения) записы-
вают в виде таблицы нижеследующим способом:
1 : 2 i 3 i Os 7 : 8 : 9 ! 10 и i 12 i в 1 'I 1 j— — > -у- 14 i 15 i 16 i 17 i 18 i 19 i 20 : 2i i 1 22 i 23
1 В ; к а • -у . К ; О • М Г • о • д : у P a • c c j ч И T • Ы В ; a • Й i 1
2 В i к а К О : Й 3 : е : М: Л e : у : Г а Д : Ы : В : a : Й : • 2
3 II: а С : Г : О : Л б : о В : о Й : Д : О p : О : Ж e : 11 : Ь : К e : 3
4 ci о Ш: Л : И : С Ь : С i С : М Ь М : у Ж : И i К : О : В : • : 4
5 С? е м ь i в i р С : >1 i е i Н II i о о б : Я i 1 i а : Н i 11 i Ы X 5
6 ni о д Т i Я : II У i Т i О i Й г i у i б Т 1 » Mi 1 • •* 4 : s 4 • 6
7 У; е 3 ; Д а : I е . р : П : И Г : и : р е i В а : : : 7
Н nj у с ; Т : О : П : « = i > : 3 : i J ’ °*i i i ; Q ; н : е : й B:o:n:o:c:T:|ti 8
9 Ир с М : е : Ж И:Ы. X : Д е р : с В С Н : 1. : 9
10 3 i а п Л : а : Т О : П : a : Д Ы : р Я В : И : Н : а : 10
II Р : Я 3 у i Т о В : a 3 : II U б : И Ш : И Н : а : : 11
12 г i о р = е i Л : о в i a : 1Г: e С i Л ° В : а • : : : : I 12
13 II i е V Р i О i Ж a i й i к i a Т io : Ж 13
14 ci о III л и • с я : и i з i a с i п i о . р i и i Л i II i i i 14
15 Ki о м у : ж: И в e T : c : я ; в : е • С : С : Л jo i 15
16 W i л ь : Г : О i T : II : О : II : a i Р ; у i i i • 16
1 i 2 3 4 i 5 i 6 : 7 i 8 ; 9 : 10 i и i 12 i ы : 14 i 15 i 16 i 17 i 18 i 19 i 20 21 22 ;
Пользуясь такой таблицей, нетрудно шифровать и расшифровывать
любое сообщение, например.
14,5 5,5 7,5 6,10 2,5 2,1 2,12 6,3 8,5 16,7 13,2 7,8 14,7 7,6 6,4 |
6,6 7,2 12,5 5,4 11,3 10,13 6,15 2,1 15,1 1,16 3,3 6,3 6,14 13,1 4,5 8,4 6,4 j
19
§3. Из истории второй мировой
войны
В воскресенье, 7 декабря 1941 г., рано утром японская авиация нанесла
внезапный удар по военно-морской базе США в Перл-Харборе (Гавайские о-ва)\
и вывела из строя основные силы американского Тихоокеанского флота. К
этому событию японцы готовились с августа 1941 г. Американцы тогда
уже умели читать военно-морскую переписку японцев Незадолго до этого
нападения японские агенты на Гавайских островах получили указание со-
общать о точном местонахождении и перемещениях военных кораблей
США. Американские военачальники и администрация президента снача-
ла не придали этой информации должного значения, и поэтому распоряже-
ние Рузвельта о превентивных мерах поступило на базу тогда, когда военные
корабли уже горели.
С конца 1941 г. наши союзники по антигитлеровской коалиции регу-
лярно формировали на английской военно-морской базе в Исландии кон-
вои - специальные соединения из транспортных и военных судов - и направ-
ляли их в северные порты СССР. Переход такого каравана судов длился
10-14 суток. Во второй половине 1942 г. в СССР был отправлен конвой
PQ-17. Внезапно где-то на полпути конвой был атакован немецкими подлод-
ками и с воздуха. В результате из 36 судов было потоплено 24, на дно было
отправлено 3350 грузовиков, 430 танков и 100 000 т разного груза. Предыс-
тория этого события такова. В июле 1942 г. финский центр радиоперехвата
принял телеграмму, переданную азбукой Морзе с советской авиабазы вблизи
Мурманска и зашифрованную несложным шифром. В ней сообщались все
данные о конвое PQ-17, его времени отправления, месте назначения, количе-
стве судов и характере грузов. В финском центре смогли расшифровать эту
телеграмму и передать ее немцам Аналогичная история повторилась и со
следующим конвоем.
§4. Криптография и археология
Многие народы, населявшие Землю, бесследно исчезли, о других оста-
лись лишь археологические памятники со следами неведомой письменно-
сти или упоминания в трудах греческих или римских историков. И лишь
иногда удается оживить эти памятники, заставить заговорить их на совре-
менных языках. Геродот в своей "Истории" сообщает, что египтяне пишут
справа налево и что они употребляют двоякого рода письмо: одно называют
священным (иератическим), другое - общенародным (демотическим). Но
уже в IV в. египетские иероглифы воспринимаются как рисуночное письмо, в
котором отдельные знаки обозначают самостоятельные понятия. Болес того,
высказываются и мнения, что иероглифы являются орнаментами и простыми
20
\ крашениями Только в эпоху Возрождения появился интерес к загадочным
иероглифам Чтобы воскресить египетскую письменность, пришлось потру-
шться многим ученым. Упомянем некоторых из них. Первый, кто пытался
оживить египетские иероглифы, был иезут Анастасий Кирхер. Он же пока-
1.1Л, что коптский язык - исчезающий язык египетских христиан - был
древнеегипетским народным языком. Датский ученый Карстен Нибур, за-
нимаясь в Каире копированием всех доступных ему иероглифических надпи-
сей, обнаружил, что число различных иероглифов невелико. Поэтому египет-
скую письменность нельзя рассматривать как целиком идиографичсскую, т е.
такую, в которой для каждого слова имеется отдельный знак. В 1799 г. при
отступлении наполеоновских войск из Египта совершенно случайно вблизи
г. Розетта был найден камень, испещренный письменными знаками. Уже с
первого взгляда можно было установить, что эта надпись состоит из трех час-
гей: верхняя составлена из иероглифов, самая нижняя - из греческих букв, а к
средней сначала и не знали, как подступиться. Розетский камень привлек
внимание европейских ученых. И только в 1821 г. Жан Франсуа Шампольон
завершил многолетнюю работу над расшифрованием египетской письменно-
сти. В результате он мог передавать демотический текст, знак за знаком, ие-
ратическим письмом и это последнее - иероглифами, на что до него никто не
был способен. Свой вклад в расшифровку египетских иероглифов внесли
также английский ученый Томас Юнг, немецкий ученый Лепсиус и многие
другие.
Клинопись была забыта даже более основательно, чем египетские ие-
роглифы. Геродот упоминает о персидских буквах, а Страбон - об
"ассирийской письменности", но ни они, ни древние евреи, видимо, нс
шали о клине как основном элементе этой письменности. Только в XIX в.
европейским ученым удалось заставить заговорить древнеперсидскую кли-
нопись. Среди них в первую очередь следует назвать Георга Фридриха
Гротенфенда.
Поразительным открытием было дешифровка хеттской письменно-
сти Дело в том, что о хеттах молчали все доступные европейцам историче-
ские источники. И только в одной книге - Библии - об этом народе говорится
в разных местах. Швейцарский востоковед Людвиг Буркхард во время одно-
го из своих путешествий вблизи сирийского города Хама нашел камень, по-
крытый знаками, отличными от египетских. Прошло несколько десятилетий,
прежде чем стало ясно, что это письменность исчезнувшего народа - хеттов.
Но только в 1917 г. чешский ученый Бедржих Грозный опубликовал труд
"Язык хеттов, его строй и принадлежность к индогерманской группе языков"
Загадочной до сих пор остается Индская цивилизация (IV—II тысяче-
летия до и. э ). Она открыта в начале XX в. По-видимому, индская цивили-
зация была культурой бронзового века. Ее города были застроены
2-3-этажными домами с водопроводом и канализацией, земледелие также
21
достигло определенных успехов: выращивали пшеницу, хлопок и другие
культуры; домашнее животноводство было представлено коровами, буйвола-
ми, свиньями, овцами... На керамике и металлических предметах сохранились
надписи. Но до сих пор неизвестен ни язык этой письменности, ни какие-нибудь
связи с народами, ныне населяющими полуостров Индостан.
До сих пор остаются непонятыми письмена древних жителей островов
Пасхи.
Ответы к шифрованным сообщениям
’ "Cogito, ergo sum” -лат. "Я мыслю, следовательно, существую".
(Р Декарт)
2"l* 2 * 4 * * 7eni, vidi, vici" -лат. "Пришел, увидел, победил".
(Ю. Цезарь. Донесение Сенату о победе над понтийским царем)
" " Festin a lente" -лат. "Торопись медленно".
4 "В чужой монастырь со своим уставом не ходят".
были люди в наше время - не то, что нынешнее племя -
богатыри..."
(К4.Ю. Лермонтов)
"Над Россией безоблачное небо ".
} "Рыба с головы гниет".
Иванову доверять нельзя явку сменить.
I лава 2.
ЦИФРОВОЕ
ШИФРОВАНИЕ
§ l. Сравнение арифметических
операций по их трудоемкости
В современных шифрующих устройствах обычно имеют де .то с боль-
шим о(»1.смом информации, записанным в цифровом виде, т. е. в виде знаков
। ihoii ниоудь g-ичной системы счисления, например двоичной или десятич-
hiiii В п|Ч)цсссс переработки этой информации приходится выполнять тс или
iHii.K арифметические действия или преобразования При этом возникает за-
i.i Li выбора эффективных приемов выполнения этих действий или преобра-
Шни, а также проблема оценки эффективности известных приемов
111 арифметических операций над натуральными числами простейши-
ми ми пиотся сложение, вычитание, а также умножение на степень основания.
Умножение и деление примерно одинаковы по порядку При оценке сложности
н|м<и»рлзований натуральных чисел можно не принимать в расчет операции сло-
♦» иин, вычитания и умножения на степень основания системы счисления.
2. /. Умножение
До 1962 г. никто не подозревал, что существует метод умножения мно-
IUHI44HI.IX чисел, более эффективный, чем общеизвестный. В 1962 г. студент
Ml V (ныне профессор) А.А. Карацуба предложил новый метод умножения
।tiiiii\ чисел. Обычный прием умножения двух 2л-значных чисел легко сво-
||| к । । четырем умножениям и-значных чисел. Метод Карацубы позволяет
1И“||||нсь юлько тремя умножениями и-значных чисел. В самом деле, запи-
ли м .’и тачное число в виде
Ап + 10я • Вп
Ц. • mi проверить тождество:
(А„ +10" В„ )-(С„ +10" 1)„ ) =
I. (10" + 1) + (D„ - С„) • (Л„ - В„) -10" + В„ • В„ (101" +10").
(Исюда и следует наше утверждение В дальнейшем этот метод был
v < нм р пн'нс 1 но ван. Установлено, что существует метод умножения двух
нк । ч ишисанных с помощью и двоичных знаков, требующий выполне-
ние in <м> ice O(nlogn loglogn) двоичных операций.
23
2.2. Возвышение в степень
Лемма 2.2. Чтобы вычислить степень пГ, где т - элемент некоторог
кольца, а п - натуральное число, достаточно выполнить не более 2[1о&л| ул
ножений.
Доказательство В самом деле, пусть 2^1 < п < 2А, к - 1 = [1о&л]. То
гда. записывая п в двоичной системе счисления, получим
»> = «?. 4- 1-. . Э 4- г. . Т24- 4- Г-. Л*-1 1 -L. 1 -L Л -L. ~
• т * *
т -m tn tn
Чтобы вычислить степень тп, можно поступить так. Сначала вычис
лить степени 1,т, т\ т2 . При этом достаточно выполнить к-
умножений (возвышений в квадрат) Затем некоторые из них следует пере
множить. Их не более к - 1. Итак, для вычисления степени тп потребуется н
более 2(А-1) = 2[Iogjw] умножений. □
3амечание. На самом деле эта оценка может быть улучшена.
Пример. Пусть а = З35. Имеем
35 = 1 +22 + 25.
Находим
b} = 32yb2 = b2,b3 = Ь2УЬ^ — Ь2,Ь$ — Ь2У а = 3 • by bs.
Итак, степень З35 можно найти, выполнив только семь умножений.
Вопрос 2.2. Пусть nt, п2, ...» пк - натуральные числа. Доказать, что
степень
мпхп2... пк
т л
можно вычислить, выполнив не более 2 log2 Я]Л2... п^ - к умножений
2.3. Отыскание наибольшего общего
делителя двух натуральных чисел
Теорема 2.3 /Ламе/. Пусть a и т - натуральные числа, а < т; тогдс
число к операций последовательного деления в алгоритме Евклида, необхо-
димых для отыскания (а, т) — наибольшего общего делителя чисел а и т, удов
летворяет любому из следующих условий:
I) к < 51g а,
3.
2)Л< -log2a.
2.4. Решение диофантова уравнения
первой степени
Рассмотрим задачу отыскания целочисленного решения уравнения вида
ax-my = l, (2.1)
24
I ic (a, m) = 1, a > 0, m > 0.
Для решения этой задачи число а = — обращают в конечную цепную
т
цюбь при помощи алгоритма Евклида’.
а - nt . Яо + «1» j
i w = ах . qi + «2, \
j "1 = аг . 42 4- «з,
аг = «з • 4- «4, j
• •• •• • •• • •• •• ••• :
i ак-г = акЛ . Як 1 4- «А, 5
: ак-\ = ак . Як 4- 0; )
Цепная дробь имеет вид: — = [70, Яi, </2,—, 9а1» а последовательности
т
{/’„} и {{2л} числителей и знаменателей подходящих дробей к цепной дроби
определяются рекуррентно:
Р-2 = 0 , РЛ = 1;
Q1 = 1 , Ci 0;
пк 0 - Рл ~’ Яп • Рп-\ 4“ Рп-2у
и> 0 = Qn ~ я» • Qrt i 4- Qni-
11\ вычисление удобно оформлять в виде таблицы.
п -2 -1 0 1 2 к-1 к
: Яп ?о ?1 Я2 ••• Як-1 Як
! 0 1 Ро Pl Р2 ... Р*1 Рк
1 0 Со Qi ^2 ... Qa 1 Qk
11о известно, что Рк • QkX - РкЛ • Qk = (-1)*1 и — = .
™ Qk
Таким образом,
Л так как (а, т) = 1,то Рк= a, Qk= nt. Поэтому
|ругими словами, пара < х, у >, где
* = (-1)*-* а.; У = (-»)*' ft 1,
п гястся целочисленным решением уравнения (2.1).
25
2.5. Решение сравнения первой степени
Чтобы найти решение сравнения a • х = 1(тш1 т), где (a, nt) = 1,
обычно пользуются алгоритмом Евклида, и тогда х = (-1)*'1 Qki (mod nt), где
{lk-\ - знаменатель предпоследней подходящей дроби разложения — в цепную
nt
дробь, или теоремой Ферма - Эйлера, которая утверждает, что если (a, ni) = 1, то
аФ(«) = j (mod nt).
Поэтому
х = a^m) 1 (mod nt).
Пример. Решить сравнение
1181 х=1 (mod 1290816).
Имеем:
1181 = 1290816 0 +1181,
1290816 = 1181 • 1092 + 1164,
1181 = 1164-1 + 17,
1164 = 17-68+8,
17 = 8-2 + 1,
8 = 1 • 8 + 0.
п 0 1 ;2 3 4 н
Чп 0 1092 j 1 68 2 ?8
рп 0 1 0 1 j 1 69 139 j 1181 •с
& 1 0 1 1092 | 1093 75416 151925 1290816
к = 5; х = (-1)4151925 = 151925 (mod 1290816).
В самом деле, 1181 • 151925 = 1290816 • 139 +1- l(mod 1290816).
2.6. Разложение на множители натуральных
чисел и распознавание простоты
Распознавание простоты наугад взятого числа, содержащего 125 и бо-
лее цифр в десятичной записи, проводится современными средствами за
несколько минут. Но разложение на множители "случайных’' чисел со 125
десятичными знаками требует при использовании самых совершенных
алгоритмов (1994 г ) миллионов лет машинного времени Появление но-
вых алгоритмов и машин вряд ли нарушит это соотношение, иначе гово-
26
I н vi .ia*r.i разложения на множители даже числа, о котором заведомо из-
feft ню, чго оно есть произведение двух простых, по-прежнему останется
Hinn- jрудной, чем определение простоты числа с таким же числом дсся-
iочных шаков.
и2. Криптосистема без передачи ключей
2. 7. Пусть абоненты А, В, С, ... условились организовать секрет-
имо переписку между собой. Для этой цели они выбирают достаточно боль-
ниц простое число р и такое, что р - 1 хорошо разлагается на не очень боль-
ши* простые множители. Если среди множителей такого числа кратных нет,
io число р - 1 называют евклидовым. Каждый из абонентов независимо один
и» ipyioro выбирает случайное число, натуральное, взаимно простое с числом
/• I: А, В, С, ... - абоненты; а, Ь, с, ... - выбранные ими случайные числа.
I hi с. абонент А находит число а из условия
а • а = 1(mod <р(р)), 0 < а <р - 1; (2.2)
IIIUIHCHT В находит число 0 из условия
b - 0 = l(mod ф(р)), 0 < 0 <р - 1, (2.3)
и, </ - секретные ключи абонента А; 0, b - секретные ключи абонента В и т.д.
11 vcn> абонент А решает послать сообщение т абоненту В; можно предпола-
инь, что-0 < т <р - 1. Тогда он сначала зашифровывает это сообщение сво-
им первым секретным ключом, находит
nil = ™а (mod р), 0 < mi < р (2.4)
и отправляет абоненту В Абонент В, в свою очередь, зашифровывает вновь
ни сообщение также своим первым ключом
т2 = mi (mod р), 0 < m2 < р (2.5)
и пересылает его обратно абоненту А Абонент А, получив обратно свое два-
* 1ы зашифрованное сообщение, шифрует его же в третий раз своим вторым
v нючом:
= mJ (mod р), 0 < т3 < р (2.6)
и вновь отправляет его абоненту В Последний расшифровывает эту шифро-
। леграмму при помощи своего второго ключа:
т4 = mJ (mod р), 0 < т4 < р.
В самом деле, из сравнений (2.4), (2.5) и (2.6) имеем
т4 = тк (mod р) ,
27
где
к = а • а • b • р (mod р -1).
В силу (2.2) и (2.3)
к s l(mod <р(р)).
Поэтому т4 = т (mod р), а так как каждое из них положительно и меньше р, то
т4 = т.
Пример. Предположим, что абоненты А и В решили установить между
собой скрытую связь без передачи ключей. Они выбрали для этого простое
число р = 23, далее абонент А выбирает случайным образом число а = 5, або-
нент В также случайно выбирает число Ь = 7.
Затем А, решая сравнение 5 - х = 1 (mod <р(23)), находит х = 9, анало-
гично В из сравнения 7 • х = l(mod 22) находит х = 19. Числа 5 и 9 — секрет-
ные ключи абонента Л, числа 7 и 19 - секретные ключи абонента В. Абонент
А решает секретно передать очень важное сообщение т = 17 абоненту В. То-
гда он сначала шифрует это сообщение своим первым ключом 5:
= 175 - 21 (mod 23).
Второй абонент, получив это сообщение, шифрует его также своим
первым ключом 7 и отправляет его обратно абоненту А:
т2 » 217 = 10 (mod 23).
Абонент А вновь шифрует полученное сообщение своим вторым
ключом 9 и отправляет новое шифрованное сообщение абоненту В:
т3 = 109 =20 (mod 23).
Получив это сообщение, абонент В расшифровывает его при помощи
своего второго ключа 19:
т4 = 2019 =17 (mod 23).
И так как 0 < 17 < 23 , то т = 17.
§3. Криптосистема с открытым ключом
В 1976 г. американцы Уитфилд Диффи и Мартин Хеллман
(Difil W., Hellman М.) - два инженера-электрика из Стэнфордского универси-
тета, а также Рольф Меркть, бывший в то время студентом Калифорнийского
универсистета, совершили замечательный прорыв в построении криптосиси-
стсм. Их работа частично финансировалась Национальным научным фондом,
и ее результаты были опубликованы Диффи и Хеллманом в статье "Новые на-
28
пр .тления в криптографии В этой статье был предложен новый принцип по-
. (роения криптосистем, не требующий не только передачи ключа прини-
м•нищему сообщение, но даже сохранения в тайне метода шифрования Эти
нн(фрь! позволяют легко зашифровывать и дешифровать текст и их можно ис-
ки и. ювать многократно. С такими шифрами мы и познакомимся. Опишем при-
а» р (акого шифра - криптосистему с открытым ключом.
2.8. Пусть абоненты А и В решили наладить между собой секрет-
th к» переписку с открытым ключом. Тогда каждый из них, независимо от
ipyroro, выбирает два больших простых числа, находит их произведение,
ф\нкцию Эйлера от этого произведения и выбирает случайное число,
кв iii.iuec этого вычисленного значения функции Эйлера и взаимно про-
к г с ним. Итак,
A: pi, р2, rA = Pip2, ф(Гч), (а, ф(гл)) = 1,0 < а < <р(гл).
В: qIf q2, rB = qiq:> <p(rB)t (b, = 1, 0 < b < ф(гв).
Затем печатается телефонная книга, доступная всем желающим, кото-
рой имеет вид:
А: га, а
В: rB, b
г а - произведение двух простых чисел, известных только
А, а - открытый ключ, доступный каждому, кто хочет
передать секретное сообщение А, гв - произведение
двух простых чисел, известных только В, b - откры-
тый ключ, доступный каждому, кто хочет передать
сообщение В.
Каждый из абонентов находит свой секретный ключ из сравнений
I (mod ф(Гд)) и by г 1 (mod ф(гв)), выбирая при этом а и 0 из условий:
s 1 (mod ф(гл))» 0 < а < Ф(гЭ, А0 я 1 (mod <р(гв)), 0 < 0 < ф(гв).
Итак,
Абонент Открытые ключи Секретные ключи
А Га, а ............... У.
В г в, b р
Пусть абонент А решает послать сообщение т абоненту В:
А: т -> В и пусть 0 < т < гв, иначе текст делят на куски длины гв.
I. А шифрует т открытым ключом абонента В, который есть в теле-
фонной книге, и находит
nti — mh (mod rB), 0 < mi < rB.
IL В расшифровывает это сообщение своим секретным ключом
тг = (mod rB ), 0 < тг < гв, и полу чает тг - ть
29
Доказательство:
nt2 smf = (nt$)b = тЛр(то(1гв);/>Р s l(mod<p(rB)),
следовательно, m2 = nt (mod гв). Но так как 0 < m < rB, 0 < m2 < rB, to nt2 = m.
Пример. Пусть pi = 7 и = 23 - простые числа A; qx = 11 и q2 = 17 -
простые числа В; г - 161 и v = 187 - произведения этих чисел соответственно
<р(161) = 132, <р(187) = 160, а - 7, b = 9 -случайные числа А и В соответственна
и наконец, пусть телефонная книга, доступная всем желающим, имеет вид:
1) А; 161,7.
2) В; 187, 9.
В этой книге первое число - произведение двух простых, известны:
только одному абоненту, второе число - открытый ключ, доступный каждому
кто хочет передать секретное сообщение этому абоненту. Каждый из абонен
тов находит свой секретный ключ из сравнений:
7а =1 (mod 132), 0 < а < 132;
90 =1 (mod 160), 0 < 0 < 160.
Таким образом, они находят собственные секретные ключи 19 и 89 а
ответственно. Пусть теперь абонент А решает послать сверхсекретное сосМ
щение т = 3 абоненту' В:
А: т = 3 —> В.
Тогда он шифрует это сообщение открытым ключом абонента В:
пц = 39= 48 (mod 187), 0 < тх < 187.
Таким образом, тх = 48. Абонент В расшифровывает это сообщение свои
секретным ключом:
т2 = 4889 = 3(mod 187),
следовательно, т2 = 3.
2.9. Надежность системы
Заметим, что в описанной выше криптосистеме с открытым ключе
для перехвата сообщения m необходимо найти секретный ключ 0. Это во:
можно в двух случаях:
1) если известно разложение гв на простые множители;
2) если известен модуль ф(гв) сравнения by =1 (mod ф(гв)).
Но так как rB = qtq2, то ф(гв) = ф(^0 ф(?2 ) = (?1 - 1)(?2 -1) = qxq2 -(qt + + q2) + 1
и (?i - qif = q] + = (?i + ?2)2 “ 4?i?2‘
Таким образом, имеем равенства.
30
= гв - (qt +q2) + 1,
(qi - Чз)2 = (<Zi + qi? - *rB,
ii шачит, зная ф(гв), можно решить эту систему и найти qx и q2, а зная q^ и q2,
iKiKO вычислить ф(гв). Таким образом, оба подхода определения ключа (3 эк-
ипналентны, т. е. задачи одной сложности
§4. Электронная подпись
Криптосистема "открытый ключ" неудобна в том смысле, что полу-
ч.нель сообщения не знает, кто является отправителем сообщения. Этого недос-
। >11 ка лишена описываемая ниже система.
2.10. Предположим, что у нас имеется банкир В и несколько вкладчи-
। пи Щ, WZ2, Из, .... Банкир и каждый из вкладчиков независимо друг от друга вы-
пирают по два больших простых числа и держат их в секрете. Пусть Р и Q - про-
। и.ю числа банкира, р„ и qn - простые числа вкладчика Wm и = 1, 2, 3, ... .
11 ,с!ь далее R = Р • Q, гп = рп • qn, n = 1, 2, 3,.... И пусть банкир В выбирает
пиершсино случайно целое число S’ с условиями 0 < Л’ < ф(Я), (S', ф(Я)) = 1, а
» 1дый из вкладчиков также совершенно случайно и независимо друг от дру-
। । выбирает число з„ с условиями 0 < sn < q>(rn\ (s„, q>(rn)) = 1. и = 1, 2, 3,....
I Ii к ле этого публикуется всем доступная телефонная книжка.
В; Я, 5
WS; п, st
И?, гг, s2;
Далее каждый из них - и банкир, и вкладчики - находят свои секрет-
ине ключи Т, t„ из условий.
ST=l (mod ф(Я)), 0 < Т< ф(Я),
t„ = 1 (mod ф(г„)), 0 < tn < ф(г„), n = 1, 2,3,....
Предположим, что вкладчик И7 = И7, собирается дать распоряжение m
поему банкиру, и пусть также г = r2it-t29s =
H<r<R. (2.7)
I In. леднее неравенство существенно для дальнейшего. Будем считать, что
»« г и (т, г) = 1. Вкладчик распоряжение т шифрует сначала своим секрет-
ным ключом:
гщ = т (modг), 0 < т2<г,
। потом открытым ключом банкира
т2 = (mod Я), 0 < т2 <R.
31
Банкир В, получив шифрованную телеграмму' т2, расшифровывает се
пользуясь сначала своим секретным ключом Т:
т3 - m2 (mod Я), 0 < m3 < R,
а потом открытым ключом л вкладчика:
т4 = wj(modr), 0 < т4 < г
и получает т4 = т.
Доказательство. Так как
т3 = м2 (mod/?),
ш2 = mf (mod Я),
то т3 = m^r(mod/?), где ST = 1 (mod ф (Я)). Если (m}, R) = 1, то по теорему
Эйлера mfТ = Mj (mod Я), т. е. m3 a тх (mod Я). Но 0 < т3 < R, 0 < тх < г < R,
следовательно, т3 = тх. Имеем
м4 = т3 = т[ = mst (mod г), st = 1 (mod ф(г)) и (т, г) = 1, а значит
т4=т (mod г), но каждое из них меньше г и больше нуля. Следовательно
эти числа равны. т4 = пи Таким образом, банкир В получит распоряжение /я
от вкладчика Ж
Пример. Пусть банкир В выбирает простые числа 7 и 13, вкладчик М
выбирает простые числа 11 и 23, таким образом, Я = 91 = 7-13 и
г = 253 = 11-23. Пусть 5 и 31 - открытые ключи банкира и вкладчика, а 29 J
71 - секретные ключи банкира и вкладчика соответственно. И в самом дела
5 • 29 = 1 (mod 72), 31 • 71 = 1 (mod 220). Тогда открытая телефонная книжка
имеет вид
В; Я= 91, а = 5;
W;r = 253, Л = 31;
Вкладчик И7 дает поручение т = 41 своему банкиру В и замечая, ч
Я < г, шифрует его сначала открытым ключом 5 банкира, а потом своим се
ретным ключом 71:
mi = ms = 41s = 6 (mod 91);
/и2=671 = 94 (mod 253).
Банкир, получив шифротелеграмму т2 = 94 и замечая, что Я < г, ра
шифровывает ее, пользуясь сначала открытым ключом вкладчика, а поте
своим секретным ключом
Wj :944 -6(mod 253),
т4 = 6г9= 41 (mod 91).
А так 41 < 91, то банкир делает вывод, что 41 и сеть распоряжение это-
lo вкладчика.
2.11. Пусть числовые данные приведенного выше примера сохра-
няется, т с. сохраняется та же их телефонная книжка и те же, следовательно,
<н крытые и секретные ключи вкладчика W и банкира В. Пусть, как и в при-
мере. т - 41. Предположим, что как вкладчик, так и банкир в своих действи-
|\ нс учитывают необходимого смысла неравенства между г и R Рассмотрим
нес возможные последовательности применения ключей шифрования (де-
шифрования) банкиром и вкладчиком. Для этой цели будем символами ОВ
и OW обозначать открытые ключи банкира и вкладчика соответственно и,
in.i логично, символами СВ и СИ7 их секретные ключи. Тогда представятся
•н.чыре варианта:
1) ОВ, СИ7 OW, СВ;
2) CW, ОВ, СВ, OW;
3) ОВ, CW, СВ, OW;
4) CW, ОВ, OW, СВ.
В самом деле, отправляя сообщение, вкладчик пользуется или своим
и кретным ключом, или открытым ключом банкира, банкир же, получая со-
|Инценис, пользуется или своим секретным ключом, или открытым ключом
•и ладчика.
Первая возможность была рассмотрена в примере. В этом случае
ж, 41s = 6 (mod 91); т2 = б71 s 94 (mod 253); т3 = 9431 s б (mod 253);
„и 629 = 41.
Пюрая возможность.
•и, 4171 = 115 (mod 253); т2 = 115s s 33 (mod 91); т3 = 3319 = 24 (mod 91);
ж, 12431 = 24 (mod 253).
I |Н 11>Я возможность
ш, * 4Is = 6 (mod 91); т2 = б71 = 94 (mod 253); т3 = 9429 61 (mod 91);
ж.» 6Iмs 83 (mod 253).
' I» । иертая возможность:
ж, - 4171 = 115 (mod 253); т2 = 115s = 33 (mod 91); т3 = ЗЗ31 = 66 (mod 253);
и, 6629= 53 (mod 91).
Таким образом, видим, что при г < R к правильному результату приво-
Ш1 юлько первый вариант применения открытых и секретных ключей.
Н< в чае R< г последовательность процедур должна быть изменена.
I lot
33
Глава 3. КОНЕЧНЫЕ ПОЛЯ
Определение 3.1. Поле F ~ < F, +, х, 0, 1 > называют конечным, сс
ли F- множество его элементов - конечно.
Обозначение. Fq — символ для обозначения конечного поля из q эле-
ментов, F* -мультипликативная группа не равных нулю элементов поля F
Если а - элемент некоторого кольца, а п - неотрицательное целое число, т
п * а - л-кратное элемента а.
Примеры:
1. Если р - простое число, то Z!- кольцо классов вычетов по моду’
лю р - конечное поле из р элементов.*
{0}Р, {!}/>» {2}р,...»{р — 1}р. (3.1)
Если a, b е Z, то
{«}р = {Ь}р о a = b (mod р).
Ддя краткости при указанном р элементы ряда (3.1) обозначаем зна
ками
0,1,2,..., р-1. (3.2)
2. Пусть р = 5, тогда таблицы сложения и умножения элементов по;
F$ имеют вид
+ 0 1 2 3 4 х 12 3 4
0 1 2 3 4 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 12 3 12 3 4 2 4 13 3 14 2 4 3 2 1
Вопрос 3.1.
В поле F37 решить уравнения
1) 17 + 19=х;
2)17-19=/;
3) 17 х 19 = z;
4) 17 : 19 = w;
5)х1 2 3-2 = 0;
6)х2-3 = 0.
34
§1. Характеристика поля
Теорема 3.1. Если Fq= < F. +, х, 0, 11 > - конечное поле из q элемен-
тч:, 11 - единица поля, то для любого элемента а из F
q * а = 09 (3.3)
и ч 1С1Н0СТИ,
q * Я = 0.
Доказательство. Равенство (3,3) следует из теоремы Лагранжа, так
। о q (число элементов) - порядок аддитивной группы поля Fq. П
Определение 3.2. Пусть F=< Е +, х, 0,11 > - поле. Если дзя любого
и нурольного т
т * 11 * 0, (3.4)
in характеристикой ноля F называют число 0, а поле F называют полем
о) (свой характсрисгики Если дпя какого-либо натурального числа т
т ♦ 11 = 0, то наименьшее число т с таким свойством называют характер»-
I 1ПКОЙ ноля F.
Пример. Любое числовое поле - поле нулевой характеристики.
I о hlно классов вычетов кольца Z целых чисел по простому модулю р -
пине характеристикир.
Теорема 3.2. Если F - подполе поля Н, пю характеристики полей F и Н
/ч шн 1.1
Доказательство. Утверждение теоремы следует из того, что единица
in hi я является единицей своего подполя □
Пример бесконечного поля конечной характеристики
Пусть р - простое число и F - поле; поле Н рациональных дробей над
пи нем F является расширением поля F и, следовательно, имеет ту же харак-
н рнстику, что и само поле F.
В частности, если характеристик;! поля F равна р, то и характеристика
и» ши II равна р.
Теорема 3.3. Характеристика поля F ненулевой характеристики
I. ть число простое.
Доказательство. Предположим, что характеристика т конечного по-
ц| / есть число составное
т = а < а < < b < т.
I In . вопству кратных единицы поля
ш * Я = (а * Я) • (Ь * Я),
i ругой стороны, т * Я = 0. А так как поле не имеет делителей нуля, то или
я ♦ И О, илиb * Я = 0, что невозможно приа<т и b <т. □
35
Теорема 3.4. Если p — характеристика конечного поля F— < F, +, х, 0.11
и т, п, k, I- натуральные числа, то
(1) т * 11 = п *11
<=> т = п (mod р),
(2) (ш * 11) + (л ♦ И) = к *11 т + л = к (mod р),
(3) (tn * 11) х (п * t) = I * 11 о т п =1 (mod р).
Доказательство.
(1) Так как р - характеристика поля F, то по теореме Лагранжа
(т - л) * 1! = 0 <=> р | (т - л). □
(2) По свойству кратных имеем
(т * 11) + (л * И) = (т + л) * И.
Отсюда и из (1) следует (2).
Аналогично доказывается утверждение (3). □
Вопрос 3.2. В каком поле 11 = -11?
Теорема 3.5. Всякое конечное простое поле F = < F, +, х, 0, И > ха-
рактеристики р изоморфно кольцу классов вычетов кольца Z целых чисел по
простому модулю р.
Доказательство. Любое подполе поля F содержит элементы
0 = 0*11, 1 = 1 *Ц, 2 * И,..., (р —1) * Ц.
(3.5)
В силу теоремы 3 4 сумма, разность, произведение любых элементов
ряда (3.5) и обратный элемент к любому ненулевому элементу1 этого множе-
ства принадлежат тому же множеству. Поэтому множество элементов (3 5)
относительно операций "+" и образует подполе поля F, а так как F про-
стое поле (т. е. поле, не содержащее других подполей, кроме самого поля F),
то это подполе совпадает с полем F.
Определим отображение С, множества (3.5) на множество классов вы-
четов кольца целых чисел Z по простому модулю р условием.-
m * 11 -»
Легко проверить, что С,- взаимно однозначное отображение, которое
сумму и произведение элементов поля F переводит в сумму и произведение
образов этого отображения. □
Теорема 3.6. Всякое конечное поле F характеристики р содержит
простое подполе из р элементов и является его конечным расширением.
Доказательство. По теореме 3.2 характеристика простого подполя по-
ля F равна р. Но конечное поле заведомо является конечным расширением
любого своего подполя □
Теорема 3.7. Число элементов конечного поля Н = F4 характеристи-
ки р есть степень его характеристики.
36
Доказательство. Пусть Fp - простое подполе поля II. По теореме 3.6
попе Н содержит элементы hb h2, ..., h„ (базис), такие, что любой элемент h
по н Н однозначно представляется в виде
Л = «1 - h2+а2 • h2+... + ап • hn,
। и , а2,..., «„-элементы поля Fr Но число разных наборов < аь а2,..., ап >
• цементов поля Fp равнорп. Поэтому q =рп. □
Теорема 3.8. Пусть Н - поле характеристики р; k е N; a, b е Н.
1ч.ч)а
(а + Ъ)р = ар + ЬР , (3.6)
(a~h)pk =apk -bp\
Нели b * 0, то
(W*
Доказательство. Докажем первое утверждение теоремы индукцией по
а 11рн к = 1 имеем
(а + Ь)р = ap + Clpap~1 b + С2ир~2 b2 + ... + Cp la bp~l + bp.
Л । ак как р - простое число, то при 1 < п < р - 1
С” = 0 (mod р) .
Но ному
С”* а^Ьп = (),
г. nt I < п <р- 1. Следовательно,
(а + ЬУ = ар+Ьр.
11* 'рсход от к к к + 1 тривиален.
* * * *
Так как (а-Ь)р = (а + (-Ь))р =ар +(-Ь)р , то второе утвержде-
на теоремы дтя нечетного р очевидно, а для р = 2 легко выводится, посколь-
Н II « -11. Остальные утверждения теоремы проверяются непосредственно. □
^2. Существование конечного поли
Теорема 3.9. Если р - простое число, п - натуральное число, q = рп,
цы tm ie разложения Н над полем Fp многочлена хч -х есть конечное поле из q
н< мттов.
Доказательство Полагаем f = хч -х Если х и у - корни многочлена
I ю । лк легко проверить, пользуясь теоремой 3 8, сумма, разность, произве-
37
денис и частное (при у * 0 ) также являются корнями того же многочлен;]
Поэтому множество корней многочлена /является подполем поля Н. В си
лу теоремы 3.1 (/)' = (хч - х)' = qxq1 - 1 = -1 # 0. Поэтому производная много
члена / и сам многочлен / взаимно просты. Отсюда следует, что его корни во
различны. L1
Теорема 3.10. Для любого натурального и и простого р существуем
конечное поле из рп элементов.
Доказательство. Следует из теоремы 3.9. П
§3. Мультипликативная группа
КОНЕЧНОГО ПОЛЯ
Теорема 3.11. Если Fq — < Fq,+t х, 0, Ц > - конечное поле, а е Fq, а * О
то
ач'х=\\. (3.7)
Доказательство. Равенство (3.7) следует из теоремы Лагранжа, так ка1
Ч - 1 - число элементов мультипликативной группы поля Fq. □
Определение 3.3. Пусть Fq — < Fq, +, х, ОД > - конечное поле; а е Fq
Наименьшее натуральное число д с условием
а£= 1 (3.8)
называют порядком элемента а поля Fq.
Обозначение, ord а - порядок элемента а.
Теорема 3.12. Если а - элемент мультипликативной группы поля Fq
то.
a) ord а q - 1
и, более того,
ord а | q - 1,
другими словами, порядок ненулевого элемента поля Fq - делитель числа
ч-Ь
б) в тех же предположениях, если п - натуральное число, то
= 1; (3.9)
в) если п - натуральное число и а-любой элемент поля Fq, то
а4 - а.
Доказательство.
а) Следует из теоремы Лагранжа.
б) Любой делитель числа q - 1 делит число qn - I.
в) Следует из б). □
38
Замечание. Если q = р - простое число, то элемент а поля Fq
можно рассматривать как класс вычетов кольца Z по простому модулю р с
представителем а:
а = где а g Z, 0 < а £ р- 1.
V' донне (3 8) в этом случае равносильно условию:
as = 1 (mod р).
I lu ному порядок любого элемента а мультипликативной группы F* поля Fq
и и. вместе с тем показатель, которому принадлежит целое число а по про-
I н>му модулю р.
Вопрос 3.3. Пусть р-1. Найти порядки всех элементов F7.
Теорема 3.13. Пусть и - ненулевой элемент порядка б поля F? п, т е N.
ат -ап <=>т = п (mod 5).
Доказательство. В самом деле, по теореме Лагранжа
</"-”=1 <=><5l m-w.D
Теорема 3.14. Пусть а - ненулевой элемент порядка б поля Fq. Тогда
• h менты
а, а™ (ЗЛО)
н«»о Fqeceразличны.
Доказательство. Следует из теоремы 3.13. □
Теорема 3.15. Пусть а — ненулевой элемент порядка S поля Fq Тогда
чг менты (3.10) - суть все корни многочлена
х5-1 (3.11)
Доказательство. При любом натуральном к
(«У = («*)* = И,
по н ому все элементы ряда (3.10) - корни многочлена (3 .11). Но многочлен
। । смени б над полем имеет в поле не более б корней □
Замечание. Утверждение теоремы 3.15, справедливое для элементов
। оиечных полей, может быть несправедливо для элементов некоторых колец.
Пример. Рассмотрим Z/«. Элемент 3 кольца классов вычетов целых
чш с.п Z по модулю 8 имеет порядок 2. Элементы 1, 2, 3, 7 все различны и все
пни корни многочленах2-1 в этом кольце.
Теорема 3.16. Пусть а - ненулевой элемент поля Fq порядка б; k е N.
Тогда
, к 5
ord а =--------,
(Л, б)
39
в частности,
ord а * = 8 о (А, 8) = 1.
Доказательство. Введем обозначение: т = ord а *. Тогда
акт=1.
По теореме Лагранжа 61 кт. Поэтому
а так как
то
_8_ к
(Л,8) (*,8)'"’
8 к 'I _
(A, 6)’(A,8)J “ *’
8
----- т.
(Л, 8)
С другой стороны,
й А_
(„*)<*•») =(а8)(».8) =1
Поэтому
т
8
(Л, 8)’
откуда и получаем, что
h
т ~ ord а -
-----.□
(*,8)
Теорема 3.17. Если а - элемент поля Fq порядка 8, то число всех
элементов поля Fq порядка 8 равно <р (8).
Доказательство Всякий элемент порядка 8 поля Fq есть корень мно-
гочлена х - 1. По теореме 3.15 элементы (3.10) - все корни этого многочле-
на. По теореме 3.16 среди них элементов порядка 6 столько, сколько чисс!
взаимно простых с 8 среди чисел ряда
0,1,2,»., 8-1. I
По определению функции Эйлера это число равно (р (8). □
Теорема 3.18. Если 8- натуральный делитель числа q - 1, то число
элементов поля Fq порядка 8 равно <р (8). в частности, число элементов по-
рядка q-1 поля Fq равно ф (g - 1).
Доказа iельство. Обозначим символом ф (8) число элементов порядка
8 поля Fq. По теореме 3.12 имеем
40
£V(8) = f-1. (3.12)
д|9-1
По теореме 3.17
V6e/V, ц/(б)<<р (б). (3.13)
I Io в силу тождества Гаусса для функции Эйлера
£<р(6) = «-1. (3.14)
Из соотношений (3.12) и (3.14) следует, что
]Г(ср(б)-ц/(б)) = О.
б|9-1
13 силу (3 13) (б) = <р (б), если 3 q - 1. I J
Теорема 3.19. Мультипликативная группа ненулевых элементов ко-
ИгЧ/М.'О поля F4 циклично.
Доказательство. В самом деле, порядок такой группы равен q - 1 А
Им icopcMc 3.18 число элементов порядка q - 1 в этой группе равно <р (q - 1).
I и нм образом, в мультипликативной группе ненулевых элементов поля F4
•ин < гея по меньшей мере один элемент порядка q—1. П
Вопросы. Доказать утверждения 3 4-3 11.
I । Любая конечная подгруппа в С ииклична.
* Никакая подгруппа аддитивной группы конечного поля если она со-
стоит не и $ одного нуля, не является линейно и строго упорядоченной.
I <| Никакая подгруппа мультипликативной группы конечного поля, если
она состоит не из одной единицы, не является линейно и строго
упорядоченной.
I 7. Только два поля Fs и F8 имеют четыре примитивных элемента.
1 Н Если Fq- конечное поле нечетной характеристики, то уравнение х + у = z в
F* имеет (q - 1) • (q - 2) решении
I ’> Гели F- конечное поле из q элементов, а е F*, б = (и, q - 1), то уравнение
хп=а (3.15)
и in нс имеет решений, или имеет б решений.
I HI Если F - конечное поле из q элементов, б = (п, q - 1), то множество тех
исмснтов из F*, для которых уравнение (3 15) разрешимо, состоит из
Ч “ *
а---------элементов.
б
I II 1хли F - конечное поле из q элементов, б = (л, q -1), то уравнение
чI * * 4 + уп = разрешимо в F*
41
Глава 4.
НЕПРИВОДИМЫЕ И
ПРИМИТИВНЫЕ НАД
КОНЕЧНЫМ ПОЛЕМ
МНОГОЧЛЕНЫ
§1. Неприводимые многочлены
Обозначении, и, к, т, q, р - натуральные числа; р - простое число; q -
степень простого р; tp(m) - функция Эйлера, ц(/н) - функция Мёбиуса; F4 -
конечное поле из q элементов; deg /- степень многочлена f
Определение 4.1. Многочлен f над полем F называют нормирован-
ным, если его старший коэффициент равен 1.
Обозначение. ач(п) - число нормированных и неприводимых много-
членов степени над полем FT
Примеры:
1. Нормированные многочлены первой, второй и третьей степени
над полем F2:
2. Нормированные многочлены первой степени над полем F$:
х, х + 1,х + 2.
3. Нормированные многочлены второй степени над полем F3:
4. Неприводимые и нормированные многочлены первой, второй и
третьей степени над полем F2:
1) deg / = 1; / =х; / =х +1; л2(1) = 2.
2) deg / = 2; /=х* + х + 1; а2(2) = 1.
3) deg / = 3; / =л? + х+1; / =x3+xz+1; а2(3) = 2.
Вопрос1 4.1. Проверить, что многочлены х4 + х3 + 1, х4 + х + 1 и
х4 + х3 + х2 + х +1 неприводимы над полем F2.
42
Теорема 4.1. Поле разложения Н многочлена
хр”-х (4.1)
1г позем Fp есть конечное расширение поля Fp степени п.
Доказательство. Всякое конечное поле есть конечное расширение лю-
о>ч1> своего подполя (Д. 3.10.). Поэтому поле Н есть конечное расширение
n.< pi 1-'р некоторой степени к. Следовательно, число элементов поля И равно
/' < другой стороны, в силу теоремы 3 9 число элементов поля Н равно р.
। - ному к - п. □
Теорема 4.2. Любой неприводимый над полем Fp многочлен степени п
I ит многочлен хр —х.
Доказательство. Можно предполагать, что п > 1. Пусть 0 - корень не-
приводимого степени п многочлена f над полем F = Fp в его поле разложе-
•н11 Тогда 0 - ненулевой элемент поля F(0) - поля, полученного путем при-
щ ишения к полю F элемента 0 Поле F(0) конечно и содержит рп элементов
КБ |ц.типликативная группа ненулевых элементов этого поля содержит рп - 1
хкпгов Поэтому 0 корень многочлена
хрЯ ’ 1 -1. (4.2)
А так как многочлен f неприводим и имеет общий корень с многочле-
н"м (4.2), то/дслит многочлен (4.2), а следовательно, и многочлен
хр -х. L1
Теорема 4.3. Неприводимый над полем Fp степени п многочлен тогда
и nio ihKo тогда делит многочлен
хр‘-х, (4.3)
ш число п делит tn.
Доказательство. Будем предполагать, что п >1 Пусть сначала нспри-
нп И1МЫЙ над полем /^многочлен f делиг многочлен (4.3) и пусть И - поле
. । нкг.кения многочлена (4.3) над полем Тогда если 0 - корень многочлена
/, и» I], с FP(O) с Н. По теореме 4.1 поле Н есть конечное расширение стеле-
ни т поля Fp, а. в силу теоремы Д. 3.9 поле Fp(0) есть конечное расширение
н< • hi Ар степени п. Из теоремы о степени конечного расширения следует, что и -
ф hi и ль числа/н.
11усть теперь п - делитель числа tn, т е. т = к • п, где к - натуральное
ив ю Имеем
/>"-= 1‘.
t i> «>п.тгсльно, число рП — 1 делитель числа рт — 1. Аналогично устанавлива-
• м чго многочлен
л’-'-!
43
делит многочлен
хр"~ 1 - 1.
( ледовательно, многочлен
хр —х
делит многочлен
хр -х.О I
Теорема 4.4. Число неприводимых и нормированных степени п мна
гочленов над конечным полем Fp равно
(4.4)
Доказательство. Имеем
^т ар{т) = рп . (4.5)
В самом деле, правая часть равенства (4.5) — степень многочлена
хр - х,
тсвая часть равенства (4.5) - число корней этого многочлена в его поле раз-
ложения. В сил}' принципа обращения Мёбиуса из равенства (4.5) следует
"%(«) = ^р-р(т).
Ж, JI
Отсюда получаем (4.4). □
Пример. аг(3) =~ (р3-рУ, а2(3) = 1 (2-2) = 2; »2(4) = 1 • (24- 22) = 3;
3 4
*2 -х =х16 - 1 = х(х+ 1) (хг+х+1) (?+? + 1) (х4+х+ 1) (х4+х3+?+х+1);
24 =124-21+4.3=1- а2(1) + 2 • а2(2) + 4 - д2(4). I
Теорема 4.5. Для любого простого р и натурального п существует
хотя бы один неприводимый степени п над полем Fp многочлен.
Доказательство. Имеем
-рп~' ~ Рп~2 - р1,
ж я
так как ц(ш) — 1 .Но
„л+1 О„л .
-р"-1 -... -р' = £—р + Р > 0.
р-1
Поэтому ар(п) > 0. □
Замечание. Большинство теорем данного параграфа могут быть
сформулировано и доказано не только для поля Fp, но и для произвольного
конечного поля Fr
44
§2. Порядок много члена
НАД КОНЕ ЧНЫМ ПОЛЕМ
Определение 4.2. Пусть р - простое число, q - степень простого р, п -
н.нуральное число, f - нормированный степени п многочлен над полем Fp,
/(0) * 0; наименьшее натуральное число <5 такое, что
/|х -1,
называют порядком многочлена f
Обозначение, ord f - порядок многочлена f
Вопрос 4.2. Определить порядки многочленов
а)х?+х +1,+х +1 и х4+л*3+а?+х + 1 над полем F2;
б) х + 1, х + 4, х + 5 над полем F?.
Теорема 4.6. Если f - нормированный многочлен степени п над полем
/>. Д0)*0,то
1 <, ord f<, рп- 1.
Доказательство. Так как deg f = п, то число возможных остатков от
к пения многочленов над полем Fp на многочлен f равно р“, в том числе р" - 1
hi личных от нуля. В ряду' изрп многочленов
х1, 2,.... ,
I' ычдый из которых не делится на многочлен f, заведомо найдется пара мно-
। оч.зенов х* и xJ (i > j), такая, что / | х1 - xJ = xJ •( х' J - 1), а так как
многочлены х и f по условию взаимно просты, ю
fIх*~'- 1
и при этом 1 < i-j <, рп- 1, откуда 1 £ ord/^ р‘- 1. □
Вопросы. Доказать утверждения вопросов 4.3-4.6.
I.J. Порядок многочлена над полем Fp равен порядку этого многочлена
над любым расширением поля Fr
| I. Если т е N и f - многочлен над полем Fp, то
f | хт -1 <Д> ord f I т.
I 5. Пусть f и g - взаимно простые многочлены над полем Fp, тогда
ord/ g = [ord/, ordgj.
I 6. Пусть » e N; f - многочлен над полем Fp, g -f”, t - наименьшее
неотрицательное целое с условием р‘ £ и. Тогда:
a) ord g = ord(/") = р‘ • ord f;
б) если к тому7 же п > 0, то
ord g < pAti 8 -1.
45
Теорема 4.7. Если f неприводимый и нормированный многочлен с не
равным нулю корнем О, то
ord/= ord 0.
Доказательство. Пусть а = ord/, 0 = ord 0. Имеем
I
Поэтому
0а=1.
Следовательно, 0 а. С другой стороны, 0,! = 1. Таким образом, не-
приводимый многочлен f и многочлен х^-1 имеют общий корень. Поэтому
многочлен f делит дЛ- 1 и, следовательно, а £ 0. □
Теорема 4.8. Если f - неприводимый многочлен степени п над полем
Fp,§ = ord f то
s| p"-l.
Доказательство. Пусть 9 - один из корней многочлена f в его поле
разложения И Так как многочлен f имеет порядок, то 0 * 0, т. с. 0 - элемент
мультипликативной группы Н* порядка рп — 1. Наше утверждение следует из
теоремы 4 7, так как по теореме 3.12
orde|prt-l. □
Определение 4.3. Неприводимый над полем Fp многочлен называют
примитивным над полем Fp, если
ord/ = -1.
Обозначение. bp(n) - число примитивных степени п над полем Fp
многочленов.
Вопрос 4.7. Доказать, что если/- многочлен над полем Fp и
ord / - -1, то многочлен / неприводим.
Теорема 4.9. Число примитивных над полем Fp многочленов степени п
равно
6р(п)=^1. !
п
Доказательство. Из теоремы 4.7 следует, что каждый корень прими-
тивного над полем Fp многочлена степени п есть примитивный элемент поля
Fp*. Верно и обратное: каждый примитивный элемент поля Fp* - корень
какого-либо степени п над полем Fp примитивного многочлена. Далее, нор-
мированные и неприводимые над полем Fp многочлены / и g тогда и только
тогда имеют общий корень в некотором расширении поля Fp, если совпадают.
Отсюда и из теоремы 3 18 и следует наше утверждение. □
Пример.
Ы4)=^^> = 2; в2(4) = |(24-22) = 3.
4 4
46
§3. Конструкция конечного
ПОЛЯ ИЗ Рп ЭЛЕМЕНТОВ
Построение поля из //* элементов. Пусть /- примитивный степени п
и 11 полем F = Fp многочлен и 0 - один из его корней в его поле разложения
I di ла F(0) - конечное поле из рп элементов, а каждый эле мет а этого поля
и -нюшачно представим в виде
а = а(0) = а0 + йцО + а202 +... + 0я-1, (4.6)
। и //о, а2у...» a„-i - элементы поля F.
С каждым выражением (4.6) сопоставим символ
< иь а2,..., >, (4.7)
। и г/,,, аъ а2у..., - элементы поля F = Fp. Напомним, что элементы поля
/ Fp мы условились обозначать знаками 0,1, 2, ...,р - 1 . Чтобы завершить
ши 1 роение поля из р" элементов, необходимо указать, как выполняются ос-
нкпные арифметические операции над символами (4.7). Сложение и вычита-
|| и. - сводятся к выполнению этих операций в поле Fp:
(а0, «1, й/1-1) + (Ло, Ai,..., Ь„_1) = (а0 + Ло, аг + Ьъ..., + b^i).
Необходимо определить произведение элементов а = (а0, ...» an-i)
и |1 (Л«, bh..., ^0 поля F(0). Рассмотрим многочлены а(х) = и0+ арс + ар?+ +
। a, jaT1 и Р(х) = Ьо + Ьрс 4- bp? 4- ... х*1 и к многочленам а(х) • 0(х) и
fl О применим теорему о делении с остатком:
а(х) ф(х) =Дх)д(х) + у(х), (4.8)
। ic у(х) = Co+CiX + fjx2 4- ... + с„_рсГ~1 е F[x], Полагая в равенстве (4.8) х = 0,
Н<н|У'1ИМ
а(0) Р(0) = у(0).
I iiuim образом,
(tfo, Hi, ..., • (*о, ^i, •••» b„^i) — (tin Ci,..., cw_i).
Чтобы найти частное двух выражений вида (4 7), а именно,
а(Ю
Р(0) ’
(4.9)
। и р(0) * 0, заметим, что многочлен р(х) и неприводимый над полем Fp
шиничлсн Дх) взаимно просты. Поэтому можно найти многочлены w(x) и
кН над полем Fp, такие, что
р(х) м(х) +/(x)v(x) = а(х) (4.10)
•• \) • м0 + wtx 4- «2х* 4-..,4- «„.tx” 1 е Fp[x]. Полагая в равенстве (4.10) х = 0,
•мп к м значение дроби (4.9), равное
и(0) = и0 4- Ml0 4- и202 4-... 4-и„_10я_1 е Fp„.
47
Пример. Многочлен f = х2 + х +2 второй степени над полем F3 непри-
водим над этим полем, гак как нс имеет корней в нём. Вычеты а + Ьх многочле-i
нов над полем F3 по модулю f образуют поле из девяти элементов. Таблицы сл<Н
женил и умножения элсмешов этого поля выглядят следующим образом (в этих
таблицах элемент поля F9, отвечающий вычету а + Ьх, обозначаем парой ab.): j
Сложение
00 10 20 01 И 21 02 12 22
10 20 00 11 21 01 12 22 02
20 00 10 21 01 11 22 02 12
01 11 21 02 12 22 00 10 20
и 21 01 12 22 02 10 20 00
21 01 11 22 02 12 20 00 10
02 12 22 00 10 20 01 11 21
12 22 02 10 20 00 И 21 11
22 02 12 20 00 10 21 11 01
Умножение
10 20 01 п 21 02 12 22
20 10 02 22 12 01 21 И
01 12 02 10 11 21 22 20
11 22 10 21 02 20 01 12
21 12 11 02 20 22 10 01
02 01 21 20 22 12 11 10
12 21 22 01 10 И 20 02
22 И 20 12 01 10 02 21
Ответы и указания к решению вопросов
4.1. Проверить, что ДО) * 0 для каждого многочлена f и что каждый
из названных многочленов не равен (х2 + х + I)2.
4.2. а) Заметим, что а? + 1 = (х + 1) (х2+х +1) и х7+1 = (х + 1) • (х3 * * б) + х +
+ 1) х (х3+ х2 + 1) для .многочленов над полем F2.
б) Равенство х3- 1 = (х - 1) (х + 5) (х + 3) верно для многочленов
над полем F7.
4.5. Полагаем т = ord f k = ord g. Имеем m | k. С другой стороны,
g | (xm -1)", но p n. Поэтому g | (xm - l)p . А так как 1
(xm-l)p = x^ -l,To/c|wpr. I
Отсюда можно вывести объявленное утверждение.
4.6. Следует из 4.4 и 4.5.
48
Глава 5.
ПОСЛЕДОВАТЕЛЬНОСТИ
НДД КОНЕЧНЫМ ПОЛЕМ
§1. Псевдослучайные
ПОСПЕЛОВА ТЕЛЬНОСТИ й ИХ
ПРИМЕНЕНИЕ В КРИПТОГРАФИИ
5.1. Введем понятие псевдослучайной последовательности и рас-
1 могрим различные примеры таких последовательностей.
Определение 5.1. Псевдослучайной последовательностью называют
in > ледоватсльность. конструируемую с помощью каких-либо арифметических ал-
|нригмов.
Примеры:
1. Для всякого н еЛ'о определим а„ равенством а„ = [я10л] - 10 [тг10и1[.
1 ° 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 •••
1 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 ...
2. Пусть а„ = [1/7 •10я[ - 10 11/7- IO'"1], я с N.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ♦♦а
I 1 4 2 8 5 7 1 4 2 8 5 7 1 4 2 6 5 • а»
3. Пусть а0 = 0, at =1 и при любом я g N a„+i = rest(a„ + а„_ъ 2).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 аа
5.2. Периодические последовательности
и их применение к локации удаленных
и быстродвижущихся объектов
(планет, спутников, ракет)
Чтобы определить положение движущегося объекта в атмосфере и про-
ipaiicTBC, используют радиолокатор Антенна радиолокатора излучает элек-
||н(магнитную энергию узким пучком. Направление этого пучка меняется при пе-
11 мпцении антенны Частота f излучения находится в пределах 2 • 108- 10*° Гц;
। шил волны X = с //- соответственно в пределах 3 см - 1,5 м (ибо скорость
к> п|~ 300 000 км/с). Когда пучок облучает некоторый объект, то часть его
pi пи отражается назад к антенне. Сама регистрация отраженной энергии
• tv । иг указанием наличия объекта в заданном направлении Но точное положе-
49
нис объекта в пространстве узнаем, только определив расстояние до него. Рас-
стояние до объекта можем определить в результате измерения времени между
моментом излучения импульса энергии и моментом прихода его отражения.
Возникают трудности в связи с тем, что объект перемещается в пространстве,
а также в связи с тем, что в атмосфере могут возникать разные помехи. По-
этому ни посылка единичного импульса, ни посылка серии одинаковых им-
пульсов не могут содействовать решению этой задачи. Задача успешно реша-
ется посылкой длинной серии импульсов, закодированной таким образом, что
эта серия воспроизводит периодическую последовательность с очень боль-
шим периодом. В результате, получив любой отраженный импульс, можем
точно определить и момент его отправления, и момент его получения (рис. 2).
Рис. 2
Приемная антенна, которая может совпадать с излучающей, также об-
ладает резко выраженной направленностью действия, что увеличивает точ-
ность локации направления. Все это вместе позволяет устанавливать точное
местонахождение непрерывно перемещающегося объекта Период порядка
1О6~220 достаточен для локации Луны, а порядка 10’ - для локации Венеры.
5.3. Периодические псевдослучайные
последовательности и их применение
в криптосистемах
Для кодирования любого множества сообщений достаточно алфавита
из двух символов. Простейшая криптосхсма, позволяющая осуществлять
передачу сколь угодно большого объема сообщения, выглядит следующим
образом.
Схема состоит из передатчика и приемника (рис 3). В передатчик
входит преобразователь В, который поступающую информацию преобразует
в двоичную последовательность {а„}.
50
передатчик
приемник
Рис. 3
н передает в сумматор С. Устройство А вырабатывает псевдослучайную пе-
риодическую последовательность {§„} с весьма большим периодом и передает
также в сумматор С. Полученные знаки а„ и 8П сумматор преобразует в по-
и товательность {сп}, руководствуясь правилами:
О + 0 = 1 + 1 = 0, 0 + 1 = I + 0 = 1. (5.1)
Выходной преобразователь Д последовательность {с„} преобразует в
1< рию электромагнитных импульсов и отправляет ее в эфир или по телегра-
фу Переданная серия попадает в входной преобразователь Д', преобразуется
* последовательность {с„}, а затем подастся в сумматор С'. Устройство А'
приемника, как и устройство А передатчика, вырабатывает псевдослучайную
последовательность {5Я} и передает сё в сумматор С*. Полученные знаки
сумматор, пользуясь правилами (5.1), переводит в последовательность {«„} и
отравляет сё в выходной преобразователь В'. В результате корреспондент
ни лучит отправленное сообщение. Для успешной работы этой схемы необхо-
шмо. чтобы устройства А и А' работали синхронно, иначе на выходе не по-
учится та же последовательность {«„}, что и на входе. Если период последо-
ппгльности достаточно велик, то практически невозможно путем подбора
н пни нужный момент для включения устройства А’. Как решается эта зада-
•III uvдет описано в дальнейшем.
§2. Алгебра последовательностей
НАД КОНЕ ЧНЫМ ПОЛЕМ
Обозначение. Будем рассматривать последовательности элементов
IM Ht /'j,
а: /Уо -> Fp (5.2)
и v пшреблять обозначение а = {ал }* _ , или короче а =
Таким образом,
хТоТ'1
а : oio (Х1
Г.Г..Г.V.
2 3:4:5
ах . а» ; (ц • as
51
Обозначение, s- множество всех последовательностей вида (5.2); о -
последовательность из 5} все члены которой равны нулю.
Определение 5.2. На множестве s определим бинарную операцию
сложение "+" и унарные операции - умножение на элемент поля "с", а
также сдвиг "г" и полиномиальный оператор соглашениями
а) Пусть а = {аЛ}Л g SJ Р={РЛ G Si ={Yx}x е S;
Vx е 7V0 Y* =ocx+0x.
Тогда последовательность у называют суммой последовательностей аир
и употребляют обозначение
у = а + р.
б) Пусть а « {ах}х е S> РНРХ е S', с е Fp;
V X G р х.= С ’ Лх.
Тогда последовательность р называют произведением элемента с на после-
довательность а и употребляют обозначение
р = с • а.
в) Далее, пусть а = {аА}Л g s, P={PJx 6 S;
VxeN0 рх= ах(1.
Тогда последовательность Р называют сдвигом последовательности а i
употребляют обозначение р =Т • а.
г) С каждым многочленом g(k) = b0 + bi • к+...+ bk • кк е /*ДХ] сопоо
тавим оператор gr, определяемый условием: если а = {аА}А е S, то
gr* а = р = {pjx е S, где V х g No рА.= Ьо -ах + Ьх- аЛ^ +... + Ьк • л^к.
Оператор gT называют полиномиальным оператором.
Замечание, Для любого неотрицательного целого к символом Т1
будем обозначать оператор, определяемый условием
{ах}х= {«Х+*}*.
Дчя каждого многочлена g(X) = b0 + • к +... 4- Ьк • X* g Fp [X] иногда символ
g1 будем заменять выражением g(T) = b0 + bi- Т +... + bk - Т *.
Обозначение Q(.s) - множество всех полиномиальных операторов н<
множестве Si
Замечание. Буквы и Г-первые буквы английских слов "sequence1
и "translation" ("последовательность" и "смещение").
Теорема 5.1. Система < s? +, о > - коммутативная группа.
Доказательство. Очевидно. □
Теорема 5.2. Система < S; +, О, {с • | с g Fp} > - векторное про
странство, замкнутое относительно сдвига.
Доказательство. Очевидно. □
Теорема 5.3. Многочлены g(X) и Л(Х) над полем Fp равны тогда i
только тогда, если равны полиномиальные операторы gT и hT, т. е.
£(Х) = Л(Х) о V б g S
gT*6 = hT»S.
52
Доказательство. Заметим, что из равенства многочленов следует ра-
венство им соответствующих операторов. Докажем, что верно и обратное
11усть g(k) = go+ gi -X +... + gk • XA, й(Х) = h0 + hi • X +... + h„, k'n и к <, m. Вве-
дем обозначения: gT* б = а = {аж}.„ б = р = Для каждого неотри-
iiai сльного целого s выберем последовательность б условием: бх=0, если
\^биб4.= 1 Еслил'^А, то получим ao = gs, ^о = к„- селит 2: $ > к, то а0= О,
р» = Л,, но так как gT • б = hT • б, то для любого к < $ £ т hs = 0, т.е.
т = к и для всякого 0 s <> к g* = Таким образом, из равенства полино-
миальных операторов gT и hТ следует равенство им соответствующих много-
членов g(X) и Л(Х). □
Теорема 5.4. Пусть g(X) и h(k) - многочлены из кольца F[X], а = {ах}ж «
Р = {РлК- последовательности из пространства S. Тогда
a) gr» (а + Р) = gr» а + р,
6)(g + A)r»a =£7«а + Лг»а,
с) gr* (hT* а) = (g • Л)г. а.
Доказательство.
а) Следует из того, что a + р = {ax+ px}.v
б) Пустьg(X) = go +gr Х + „.-Х\ h(k) = Л0 + /»гХ+... +hm’km, к<,т.
Для каждого к <Л<т положим g, = 0. Имеем
(g + Л)г• a = (g0+ Ло) Хх + (gi + ЛО Хх+1 +... + (gm + hm) Kc+m = gT* a + hT»cL.
в) Аналогично б). □
Теорема 5.5. Система < О(^); +, •, 0 > - кольцо, изоморфное кольцу
многочленов Fp[X].
Доказательство. С многочленом g(X) = g0+ gi • X +... + gk • XA e АДХ]
сопоставим оператор gT= go + gi - T +... + gk- 7* e O(.s). В силу теоремы 5.3
но соответствие взаимно однозначно. Операции сложения и умножения для
операторов из О(.^, как обычно, определяются соотношениями:
gT+ hr = uT <=> V 5 е S uT»8=gT^8 + hT • б,
gT • hT= vr сэ\/8е$ vT • б = gr» (hT» б).
Отсюда и из теоремы 5.4 следует, что отображение g(X) -> gT сугммс и
произведению многочленов кольца /^(Х] ставит в соответствие сумму и про-
и жедсние операторов из Q(s). □
§5. /7ИНЕЙИЫЕ РЕКУРРЕНТНЫЕ
ПОСПЕЛОВА ТЕНЬНОСТН
НАД КОНЕЧНЫМ ПОЛЕМ
Определение 5.3. Пусть р — простое число; at, а2,..., а„ е Fp, а„* 0.
Уравнение вида
5х+л = «1 • ^л+п-1 + «2 • 8д^-2 + — + "л • (5.3)
называют линейным рекуррентным уравнением над полем Fp порядка п,
многочлен f (X) = X"- at • Xй"1 - ... - а„ - характеристическим многочле-
53
ном уравнения (5.3). Последовательность 8 элементов поля Fp, удовлетво-
ряющую уравнению (5.3), называют также решением уравнения (5.3) над
полем Fp. Члены 80, 8f, 82,8„_i последовательности 8 однозначно опре-
деляют всю последовательность 8 и называются се начальными членами.
Решение линейного рекуррентного уравнения называют часто линей-
ной рекуррентной последовательностью.
Обозначение. S(f) = s^f) — множество всех решений уравнения
(5.3) над полем F- Fp с характеристическим многочленом f
Пример. /? = 2, и = 3, /= X3 - А. - 1. Список всех решений над полем
Ft уравнения
8Л+з = 8.V+! + 8*:
X 0 1 | 2 3 [ 4 j 5 6 7 | 8 9 j ...
8х 1 0 1 j 0 j 1 1 1 = 0 fl ; ...
5* 0 0 i i ° 1 i 1 1 0 i 0 1 i ...
8Х 0 1 0 1 : i j 1 0 0 1 fl i ...
8х 1 0 : 1 1 i j 0 fl 1 = 0 1 j ...
8х 0 1 1 1 i 0 = 0 1 0 : 1 1 : ...
Ьх 1 1 I 1 0 1 0 1 0 1 : 1 1 : ...
Ьх 1 1 i о 0 1 j 0 1 1 i 1 o i ...
Ьх 0 0 j 0 0 i ° i 0 0 0 ! fl 0 i ...
Теорема 5.5. Число решений уравнения (5.3) равно рп, в том числе
р"-1 ненулевых. Итак, | S (/) | = />"=pdegf.
Доказательство. Число решений уравнения (5.3) равно числу корте-
жей < 8q, ..., 8„_i > из элементов Fp, а следовательно, равно рп. □
Теорема 5.6. Пусть 8 = {8Х}Х- какое-нибудь решение уравнения (5.3),
х и у - неотрицательные целые числа. Если
8Х — ..., 8_v+n_t — 8y+n-i>
то бх+я = 6>+л, если к тому же х > 0л у > 0, то 8x_j = 8^.
Доказательство. Очевидно. □
Теорема 5.7. Пусть S (/) - система < s(f); +, {с • | с е Fp} >. Тогда:
а) Система S (/) есть векторное пространство над полем Fpt замк-
нутое относительно сдвига
б) Для любого решения 8 е s(f) = и многочлена g е ГДХ|
g". 6 е 5(/).
в) Пространство < +, {с • | с е Fp} > изоморфно пространству Vn.
Доказательство. Утверждения а) и б) легко проверяются
54
в) Зададим отображение Т:
Т: s(f) -> К,
4х: 5 -> <80,81,...,8л_1 >
•« н., как легко проверить, изоморфное отображение системы {c-\ceFp}>
ил систем}' < Vn; +, {с • | се Fp} >. □
Определение 5.4. Решение 6 уравнения (5.3) называют главным ре-
шением этого уравнения, если набор решений <5, /• 5, т1 • 5,..., тп 1 • 8 >
•iniiяется базисом пространства s(f).
Пример. Решение р = {рЛ }Л. с начальными значениями:
Р(| = Р1 =... = рл_2 = 0, рл-1 = 1 является главным, так как векторы
< 0, 0,..., О, 1 >,
< 0, 0,..., 1, рл >,
< 1, Рл» •••>Р2л-3» Р2л-2 >
шнейно независимы и, следовательно, образуют базис пространства V„.
Теорема 5.8. Любое решение 8 g S(f) уравнения (5.3) периодично,
другими словами, существует такое натуральное число т, что для любого
’ ' Ao = 5.V
Доказательство. В силу теоремы 5.6 достаточно доказать, что сущест-
ву км такие неравные натуральные числа Ли/, что
5* ~ О/, 8л+1 — 8/+1,..., 8*+„_i - 8/+я_1.
(5.4)
Но это так, так как число всех различных наборов вида < Ьи ЬгуЬ„ >
и.«и полем Fp конечно и равно рп. Поэтому, если Л > I и x-k-l наименьшее
ни. по со свойством (5.4), то т <. рп - 1. □
Определение 5.5. Наименьший натуральный период т решения 8
i равнения (5 3) называют примитивным периодом решения 8.
Обозначение, per 8 - примитивный период решения (последователь-
но! nt) 8 уравнения (5.3).
Теорема 5.9. Если F -Fp, Зе s(f) = sF(f\ f е то per 8 <,pf -1.
Доказательство. Число различных наборов < 80,8И...»8«_i > равно рп.
Если <8о, 81, ..., 8„_i > = <0, 0, 0 >, то 8= {0}х и
pi । 8 e 1 <,рп — 1.
Если < 80, 81,..., 8rt_i > * < 0, 0, 0 >, то для любого х £ О
Л., 8х+1, ..., 8х+я_! > * < 0, 0,..., О >, а число ненулевых кортежей
> равнорп -1 и даже если все они встретятся, то при некотором
। / - 1 < 8о, 8Ь8^.1 > = < 8„ 8t+1,..., 8^, >, а значит, per 8 < рп - 1. □
55
§4. Аннулирующие многочлены
Определение 5.6. Многочлен f над полем F называют нормирован-
ным, если его старший коэффициент равен 1.
Определение 5.7. F=FP, 8 е S’(/) = sF(f\ g е
Если gT • 8 = о, то многочлен /называют аннулирующим последова-
тельность 8.
Обозначение. Пусть F - Fp, АД 8) = А(8) - множество всех над полем
Fp многочленов, аннулирующих последовательность 8.
Примеры.
1. Пусть 8 - решение уравнения (5.3) и t = per 8. Тогда
(7 1) • 8 = {8^t - 8Х}Х ={0}х=о.
Итак, V- 1 - аннулирующий многочлен решения 8.
2. Характеристический многочлен уравнения (5 3) аннулирует любое
решение (5.3).
Доказательство. Пусть б = {8х}хс s(/),/=Хя-а1А,я_1-„.-аи_1Х-а«.
Если fT • 8 = ос = {<xA}.v то для любого х > О
ОСХ Нп8х — fln-lSjc+i ... Olbv+rt-i + 1 • 6х+л бг+л Т Л^8 х+я-2 ••• ^/|б
х). Но {8Х}Х- решение (5.3), следовательно, для всякого х £ 0 сс,:=0, т. е. а = {0}^ О
Теорема 5.10. Пусть 8 е S - последовательность над полем Fp,
f = ,kn -Ojl"-1 - ...-ап - нормированный многочлен над полем с неравным
нулю свободным членом. Оператор f 7 аннулирует последовательность 8
тогда и только тогда, если 8 - решение линейного рекуррентного уравнения
с характеристическим многочленом f.
Доказательство. Если 8- решение (5.3), то / е А(8), как доказано в
примере 2.
Пусть/ Т аннулирует последовательность 8, то есть / т • б = а = {0}х,
где f-'kn - лД”-1 -... - o„_A - а„. Воспользуемся определением полиноми-
ального оператора fT и вычислим любой элемент осх последовательности а:
<Хх U„^x ~ ®И-1б.х+1 ••• ~^1бх+л-1 1
Так как осх = 0, то б хЧя = at8 +... + л„8 „ т. е. 5 = {8Х}Х - решение
(5.3). □
Теорема 5.11. Пусть б е s(f), F = Fp; u,v е /4^(6) =Л(8); и» е
Тогда
а) и + v е /4(8), u-ve /1(8),
б) и • w е /1(8).
Доказательство. Пусть ит» 8 = о, у7* 8 = о, w е Fr|X|; тогда в силу
теоремы 5.4:
(мг+v7)«8 = w7*6 + v7« б = о + о = о; (ит- v7) • 8 - «'• б - v7« б "0-0 = о;
(« • w)T • 8 = (н> - й)т • 8 = wT • (ит* 8) = н,г» о о. 11
56
Определение 5.8. Пусть 5 е $(/); нормированный и наименьшей
г пени многочлен из/1(5) называют минимальным многочленом решения 5.
Обозначение. Пусть 5 е .?(/), /«^(Х) - минимальный многочлен ре-
ш« пня 8.
Примеры:
3. Если 6 = о, то wfi(X) = 1;
4. Если V х е Л'о 5,гц = бх & б о, то ws(X) = X — 1;
5. 8 Ф о <=> deg ws(X) > 1.
Теорема 5.12. (Основное свойство минимального многочлена.) Мно-
оччен g над полем F = Fp принадлежит A f{6) = Л (б) тогда и только тогда,
I. чи g делится на минимальный многочлен решения б.
Доказательство.
1) Если
#(Х) = т& (X) • h (X), где А (X) е ГДХ], то g(X) е /1, (5) в силу теоремы 5.11.
I [ели #(Х) е Лг(5), то по теореме о делении с остатком имеем
g(X) = ms(X) • А(Х) + г (X), где А(Х), г (X) е ГДХ] и deg г (X) < тк(Х).
А так как многочлен mfi(X) минимальный, то г (X) - нуль-многочлен. □
2) Из теоремы 5 11 следует, что /Ъ<5) идеал кольца FP|X|. Но кольцо
ММ - кольцо главных идеалов. (Второе доказательство.) □
Теорема 5.13. Минимальный многочлен главного решения уравнения
(5.3) есть характеристический многочлен этого уравнения.
Доказательство. Пусть б - главное решение уравнения (5.3), g = ти5(Х) -
сю минимальный многочлен, f — характеристический многочлен уравнения
(5 3). Так как f аннулирует решение 5 (см. пример 2), то g - делитель /
следовательно, deg g deg/. Но любое решение уравнения (5.3) линейно
выражается через главное решение и его сдвиги, поэтому g аннулирует любой
элемент из множества s(f). Отсюда и в силу теоремы 5.10
А’ (/) с ЭД.
11оэтому
ndeg/ < Mdcgg
р ь р >
следовательно, deg /<degg. □
Теорема 5.14. Пусть 5 е S (/), тогда
per б = ord /ns(X).
Доказательство. Введем обозначения
т = per 5, t = ord m6(X). Тогда для любого х е No 5Х= бх+t. Следовательно,
(f- 1) • б = о. Поэтому t <. т. С другой стороны,
т5(1) | г- 1,
следовательно, 1) • б = о, т е., Vx е /Vo, 8v+t= 5Д, Поэтому т < t Срав-
нивая два неравенства, получаем утверждение теоремы 1
57
Теорема 5.15. Если характеристический многочлен /уравнения
неприводим, то
f= ntf/k)
для любого ненулевого решения 5 этого уравнения.
Доказательство. В самом деле,
(5.
ms(l) I f
А так как deg m6(X) £ 1 и f неприводим, то равенство (5.5) верно. □
Теорема 5.16. Если характеристический многочлен уравнения (5.
неприводим, 8 - ненулевое решение этого уравнения, то
per 8 | рп- 1,
в частности, per 8 =р" - 1, если f - примитивный многочлен.
Доказательство. Из теорем 5.13 и 5.14 следует, что примитивный ли»
риод решения 8 равен порядку характеристического многочлена уравнении
(5.3). Утверждение теоремы следует из того, что характеристический много,
член неприводим, а его степень равна л. D
Теорема 5.17. Если 8 - главное решение уравнения (5.3), то
per 8 = ord f.
Доказательство. Следует из теоремы 5 13.0
Определение 5.9. Максимальной линейной рекуррентной последо-
вательностью порядка п называют линейную рекуррентную последователь-!
ность, если она является главным решением линейного рекуррентного урав-|
нения с характеристическим многочленом степени п.
§5.Регистр сдвига
Под регистром сдвига понимаем электронную схему, позволяющую
вырабатывать последовательность, определяемую линейным рекуррентным
уравнением.
Опишем электронную схему, физическая реализация которой позволяет
вырабатывать псевдослучайную двоичную последовательность, задаваемую ли-
нейным рекуррентным уравнением. Схема составляется из двух элементов. Один
из этих элементов называют сумматором, второй - задержкой или ячейкой
памяти. Сумматор имеет два входа и один выход. Задержка имеет один вход и
один выход Сумматор функционирует следующим образом (рис. 4).
сумматор
задержка
Рис. 4
58
Если на оба входа подаются одинаковые сигналы (0 и 0 или 1 и 1), то
,|п nt л ход подается 0; если на входы подаются разные сигналы, то на выход пере-
fti it I Таким образом, сумматор реализует двоичную функцию - сумму
| /м Если на вход задержки подастся какой-нибудь сигнал (0 или 1),
III и па выход передается тот же сигнал Рассмотрим подробнее несколько
|ц»м Схема 1 (рис. 5) отвечает уравнению:
(5.6)
Схема 1
Рис. 5
Выбирая первоначальное заполнение следующим образом:
Ан» 1,81= 0,82 = 0,83 = 0,84=0, получим периодическую последовательность:
100001010111011000111110011010010000... с примитивным периодом,
равным 31.
Схема 2 (рис. 6) отвечает уравнению
бх+5 = 8Л + 8.
(5.7)
Схема 2
Рис. 6
Первоначальное заполнение 80 = 1, 8,= 0, 82 = 0, 83= 0, б4 = О
уравнения (5.7) порождает периодическую последовательность
10000111110101001100010000 ... с примитивным периодом, равным 21.
Первоначальное заполнение 8о = 0, 8t = 1,8? = 1, 83= 1, 84 = 0 порождает
периодическую последовательность 01110010111... с примитивным периодом,
равным 7. Первоначальное заполнение 8о = 1, 8t = 1, 62 = 0, 83 = 1, 84 =1 по-
рождает периодическую последовательность с примитивным периодом, рав-
ным 3: 110110110...
Уравнению
8
(5.8)
отвечает схема 3 (рис. 7):
59
Схема 3
Рис. 7
Уравнение (5.8) имеет одно ненулевое решение - периодическую по-
следовательность с примитивным периодом, равным 15:
100011110101100100011110101100...
Уравнению
+ 8^ +8л+2 + 8х+з (5.9)
отвечает схема 4 (рис. 8), порождающая три ненулевых последовательности с
равными примитивными периодами (= 5):
10001...; 11110...; 01001....
Схема 4
Рис. 8
Уравнения (5.6), (5.7), (5.8) и (5.9) имеют соответственно характери-
стические многочлены Xs + X3 + 1, Xs + X4 + 1, X4 + X3 + 1, и X4 + X3 + X2 + X +
1, порядки которых равны соответственно 31, 21, 15, 5. Второй из этих мно-
гочленов приводим, остальные неприводимы над полем F2.
Рассмотрим решение уравнения (5.6):
10000101011101100011 11 100110100 (5.10)
Заметим, что на периоде этой последовательности любой ненулевой
набор из пяти знаков 0 и 1 встречается и только один раз. Если с набором
< а0, аь а2, а3, а4 > сопоставить число 1а0 + 2l«i + 22а2 + 23ал + 24а4, то после-
довательность (5.10) можно рассматривать и как последовательность чисел:
1 16 8 20 10 21 26 29 14 23 27 13 6 3 17 24 28 30 31 15 7 19 25 12 22 11 5 18 9 4 2 ...
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
60
I пава 6.
ДИСКРЕТНЫМ
ЛОГАРИФМ
§1. Экспоненциальный открытый ключ
6.1. Предположим, что два удаленных корреспондента А и В регу-
|ц|1но обмениваются шифрованными сообщениями при помощи описанной в
। ынс 5 схемы. Допустим, что при шифровании и дешифровании используется
и» • ндослучайная последовательность. Для успешной работы шифрующих
v гройств необходима их согласованность Точнее говоря, необходимо,
нобы у двух корреспондентов в шифрующих устройствах, начиная с
пир-деленного момента, вырабатывалась одна и та же псевдослучайная
шн ясдовательность
Предположим также, что корреспонденты А и В обмениваются сооб-
.... на языке конечного поля F^„. Чтобы добиться согласования в рабо-
• v .моих шифрующих устройств, вырабатывающих псевдослучайную после-
ши цельность, они поступают следующим образом. Прежде всего они каким-
HI способом договариваются о выборе примитивного элемента g поля F „.
Lit см они независимо друг от друга выбирают целые числа первый а, вто-
рив р, такие, что
1< а < 2", 1 < Р < 2я.
Далее, первый из них вычисляет второй - а затем они обмени-
•ннотся результатами. Получив сообщение - элемент поля F2«, первый
►оррсспондснт возвышает этот элемент в степень а, а второй, поступая ана-
ни ично, - элемент ga возвышает в степень р.
Таким образом, они получают искомый общий ключ, так как
g'^g^
(6.1)
hoi общий ключ в заранее обусловленное время они и закладывают в шиф-
р\ ни нес устройство, вырабатывающее псевдослучайную последовательность.
Предполагается, что противнику известен примитивный элемент g,
пи гунна и зашифрованная последовательность знаков и сообщения ga и g^ ,
но неизвестны случайные числа аир корреспондентов А и В. Перед ним
in i.ici задача, как из этих данных определить общий ключ (6.1) корреспон-
। шов А и В.
61
§2. Вычисление дискретного логарифм,
6.2. Определение. Пусть G = < G; •, 1 > - конечная группа, а и b
элементы группы G; г = ord b. Натуральное число I называют дискретны
логарифмом элемента а при основании Ь, если
Ь1 = л,0^ 1<г.
(6.2)
Замечания.
а) В качестве группы G избираем мультипликативную группу из йену’
левых элементов конечного поля Fr
б) Если q = р - простое число и Ь - первообразный корень по модули
р, то число /, определяемое условием (6.2), называют индексом числа а при
основании b по модулю р.
в) Вместо термина "дискретный логарифм элемента а при основании
Ь" употребляют также термин "индекс элемента а при основании Ь".
Обозначение, ind^a - дискретный логарифм элемента а при оснований
Ь. (Группа G обычно подразумевается из контекста.)
Пример. Рассмотрим конечное поле Fy. из девяти элементов, постро-
енное в примере §3 гл. 4 В качестве группы G возьмем мультипликативную
группу < F9\ { < 0,0 > }; •, < 1, 0 » поля F9. Пусть 6 = < 1,2> и о = < 2,1 >;
нетрудно проверить, что дискрстныйлогарифм а по основанию b в этом слу-
чае равен 3, но дискретный логарифм элемента < 1, 1 > по тому же основа-
нию нс определен.
Таблица индексов (дискретных логарифмов) элементов этой мультип-
ликативной группы при основании b = < 0,1 > имеет вид
10 01 12 22 i 20 02; 21 i 1£
ind a : 0 = 1 2- 3 = 41 5i 6 = 7
6.3. Задача определения дискретного логарифма эле-
мента конечной группы может быть легко решена, если порядок группы не
слишком велик и для этой группы составлена таблица индексов. При отыска-
нии логарифма положительного действительного числа, если нет таблицы
логарифмов или она недоступна, можно воспользоваться методом последова-
тельного приближения Он состоит в следующем. На каждом шаге приме-
нения этого метода интервал границ значения арифметического логарифма
сужают вдвое. Так продолжая, легко определить значение этого логарифма с
любой заранее объявленной точностью. Успех применения этого метода ос-
нован на использовании свойств неравенств. Ничего подобного нет в конеч-
ном поле. Точнее говоря, в конечном поле нельзя построить метод вычис-
ления дискретного логарифма, подобный методу последовательного при-
ближения. В самом деле, в конечном поле нельзя определить антисиммет-
ричное, транзитивное, связное бинарное отношение, согласованное с какой-
нибудь операцией (Вопросы 3 5 и 3.6 )
62
6.4. Алгоритм перебора - метод, который хотя бы теорети-
чески может всегда привести к успеху. Он состоит в следующем. Пусть b —
примитивный элемент данного конечного поля и a - другой какой-нибудь
исмент того же поля Чтобы найти ind^u, начиная, например, си = О, срав-
ниваем элемент а с элементом Ьп , если a = bn , то ind* a = n, в противном
случае находим An+I = Ьп • b и опять сравниваем элемент а с элементом
/>"+1 и т.д Если число элементов поля 21<ю или больше, то количество опера-
ций (умножений), необходимое для вычисления дискретного логарифма про-
извольного элемента конечного поля в приемлемое время, чрезвычайно велико и
находится за пределами возможностей современных вычислительных машин.
6.5. Алгоритм согласования
Теорема 6.1. Пусть t, г - натуральные числа, г1 > t. Для любого цело-
го I можно указать целые числах и у такие, что
I = хг + у (mod /);
0^ х<г, 0^ у<г.
Доказательство. Можем предполагать, что 0 <> I <t Полагаем
у = 1-хг.
Имеем
С другой стороны.
0 <; х г.
г г
0 х <, — < х + 1,
г
поэтому
или
хг<, I <хг + г
0 l-xr-у <г. □
Теорема 6.2. Пусть G = < G; •, 1 > - конечная группа; а и b - эле-
менты группы G; t = ord b;
bl-a. (6.3)
Тогда число I можно найти, выполнив не более чем 2(VF + log2/) — 1 опера-
ции умножения на элементы группы G.
Доказательство. Полагаем г = [ Л ] + 1. Рассмотрим ряды
(6.4)
o.e-jT1 г,а Ь-г г...a b^r-l)r. (6.5)
Если Ь1 - а разрешимо относительно /, то по теореме 6.1 представим Z в
виде
63
l=y+x-r (mod t), О £ X < г, О <,у < г.
Так как t = ord b, то bx = bxr+y = а в том и только в том случае, когда
bv = ab~xr, (6.6)
т.е. когда найдется элемент ряда (6 4), который совпадет с каким-нибудь
членом ряда (6.5).
Нетрудно сосчитать число операций, позволяющих установить равен-
ство (6.3). При вычислении элементов ряда (6.4) потребуется выполнить нс
более г-2 умножений. Для вычисления b~r = bf~r в силу леммы 2.2 требу-
ется выполнить не более чем 2 log2t умножений. И не более чем г - 1 умно-
жений потребуется для вычисления всех членов ряда (6.5). Поэтому общее
число операции для решения уравнения (6.3) не превосходит
2г—3 + 21og2f <. 2(Vf +log2Z)- 1. □
Теорема 6.3. Пусть G = < G; •, 1 > — конечная группа; а и b -|
элементы группы G; t = ord b; bl — а. И пусть, кроме того, число t со-
ставное:
t = ri^
1 < Tj < t, 1 < r2 < t.
Тогда дискретный логарифм элемента а по основанию b можно вычислить,
выполнив не более чем за 2(Jrl + Jr2 ) + бк^г^ + 2к^г,- 1 операций.
Доказательство. Нетрудно заметить, что любое целое число I с усло-
вием 0 1 < t однозначно представимо в виде.
1 = Г? * Л + »h; Л»Mie Z,
О < < Tj, 0 <,тх< r2.
Равенство b1 = а можно записать в виде
Возводя обе части равенства (6.7) в степень и замечая, что t = гх г2, полупим
br,mi =ari.
А это удобно записать в ваде
. nt.
*1 =а
(6.8)
где bx = ЬГ1, at = аг*.
Легко проверить, что ord bt = . По теореме 6.2 дискретный логарифм
по основанию т.е. можно вычислить при помощи не более чем
2 (^+log2 ъ) -1 операций. Из равенства (6.7) сразу получим
64
b2' = a2, (6.9)
i де b2 = bn, a2 - a • b .
Аналогично, Л можно вычислить при помощи не более чем за
2(7'7 + bg2 А) “ 1 операций. Далее, Ь^ Л2, аг можно вычислить соответст-
иенно не более чем за 2log2ri, 2 log2 П, 2 log2r2 и 1 + 2 log2/ операций. Отсю-
да и следует наше утверждение
Замечание. Здесь и дальше при подсчете числа операций, необхо-
димых для вычисления индекса элемента конечного поля, учитываем только
число умножении в конечном поле и нс принимаем во внимание любые логи-
ческие операции и операции в поле рациональных чисел, если такие потребу-
емся выполнять.
Теорема 6.4. Пусть сохраняются условия теоремы 6.3. Если
гр г2, “ натуральные (>1) числа, ord b = t и t = rt.r2.r3, то для вычисле-
ния индекса элемента а при основании h достаточно выполнить не более
2(7^ + 7Г2 + 7*7) * (6|°Й2г1',2'‘з + 6Iog2ri r2 + 2log2r1 - 1
операций.
Доказательство Пусть, как в теореме 6.3 Ь1 = а , и пусть /и гщ - це-
пью, I = r3/t + тх, 0 тх < r3, (I < lx < гхг2 ; тогда
hr>1' 'т'=а, Ьг^ = а'Л .
11олагасм
Ьх = Ьг'\ах = а'Л.
I Imccm
b™' = ах, ord bt = r3, 0 тх < г3; ЬГу1' = a-b т‘.
(хюзначим
b2 = br\ а2=а-Ь
I Ю.тучим
^2* ~ а2 > 0Г(1^2 ~ Г\ ’ г2 •
Оценим количество операций, достаточное для выполнения всех про-
межуточных шагов. При этом воспользуемся теоремами 6 2,6.3 и леммой 2.2:
2log2v2, 2log2/ir2, 2^ + 2log2r3 -1,
2 log2 F3, l+21og 2 rxr2r3, 2(7^ + 7^) + filogxFin + 21og2Ft - 1.
Итак, общее число операций равно
2(7^Г + 7^ + 7^) + 6 ,°Е2г1'2гз + GlogzHn +2к^п- 1.
1-164
65
Теорема 6.5. Если t — r\ • г2 • ... • гА~ц — есть произведение натураль-
ных чисел, то решение уравнения (6.2) можно найти, выполнив не более чем
+—+ Vr*+i ) + Лл+1+ Мс+1 операций. При этом величины
Л*+/ ~ ^к+\(гь Гг, —> rx+i) w Мы=г2,Гк+i)
определяются условиями:
Ла+1 = Л*(Г1, Г2, ..., Гк) + 61082^2^... ГА + 1 ;
Mk+i — Мк — 5 .
Доказательство. Чтобы оценить верхнюю границу7 числа операции,
достаточную для отыскания индекса а при основании Ь, как и ранее, предста-
вим число / в виде:
z = 'i+i^i + ™t,
где Wi и /1- целые с условиями 0 Zt < rt ... rft, 0 £ < гЛ+1.
Тогда получим
+"*' = а.
Так как ord b = гх г2 •... • гЛ+1, то br' "'г* ж* = аг'" 'Гк. Введем обозначения:
Ьх = Лг* 'r*, aj = а' г*. Поэтому имеем
b”1 =fli,ord^ =rAu.
Далее находим
У**’4* = а-Ет'.
Полагаем теперь Ь2 = У**1, а2 = а • b . Тогда получим
Ь2 = а2,ог<\Ь2 -гх ...гк.
Оценив количество операций, достаточное для выполнения всех про-
межуточных шагов, и применив индуктивное предположение, получим объ-
явленный результат. □
Вопросы.
6.1. Числа М(п) = 2я - 1 называются числами Мерсенна.
Известно каноническое разложение на простые множители числа Мер-
сенна: М(55)=23 • 31 - 89 • 881 • 3191 • 201961.
Оценить количество операции, необходимых для вычисления дискрет-
ного логарифма элемента поля
при использовании:
а) алгоритма перебора,
66
б) алгоритма теоремы 6.2,
в) алгоритма теоремы 6 3,
г) алгоритма, описанного в теореме 6.4,
д) алгоритма, описанного в теореме 6 5, представив М(55) в виде про-
н ведения четырех сомножителей.
За основание дискретного логарифма принимается примитивный элемент
поля.
6.2. Решить tv же задачу для поля F м, если известно, что
2
М(31) = 2147483647 - простое число Мерсенна.
§3. Историческая справка
Задача отыскания оптимального алгоритма вычисления дискретного
км арифма принадлежит к числу важнейших в криптографии Алгоритм тео-
ремы 6.2 был открыт А.О. Гельфандом в 1962 г., а алгоритм теоремы 6.3
ныл найден В.И. Нечаевым в 1965 г
Впоследствии в 1972 г. В.И. Нечаев установил (30], что среди детер-
минированных алгоритмов нет лучших в определенном смысле алгоритмов,
чем описанные в теоремах 6.2 и 6.3.
В широко доступной литературе [22, 27, 49] алгоритмы теорем 6 2 и
о 1 называют алгоритмами Сильвера - Поллига - Хелмана (Silver - Pohlig -
Hellman).
До последнего времени продолжаются исследования в отыскании дру-
и<\ (не детерминированных) алгоритмов вычисления дискретных лога-
рифмов. Были предложены такие алгоритмы, использующие вероятност-
ные соображения [27, 45, 47]
67
Ответы и указания к решению вопросов
6.1. а)г-1 = 3,6 -Ю16
б) Имеем
2(V?+log2 0-2 = 2^72 + 110 -2 = 1,9 18я.
в) Выбираем
гх = 23 • 31 201961 = 143 998 193, г2 = 89 • 881 - 3191 = 249 419 029;
имеем
2(7'? + 7^) + 61og2 rxr2 + 21og2 rx - 7 < 31531 + 311 + 51 - 7 = 31886 « 3,2 - 104;
2(11 999,9247 + 15 793,0057) + 6 • (27,10147 + 27,89399) + 2 - 27,10147 - 7 =
= 55 585,8608 + 329,972 + 54,20295 - 7 = 55963,036 = 5,6 • 104.
г) Выбираем
г, = 201 961, r2= 89 *3191 =283 999, r3=23-31 -881 =628153;
имеем
2(7^ + 7^ + Я) + 6tog2 гЛгз + 6*°ёг1г2 + 2Iog2 rt- 12 = 2(449,4007 +
+ 532,9155 + 796,1513) + 14 • 17,623 + 12 • 18,115 + 6 - 19,273- 12 =
= 3556,935 + 246,722 + + 217,38 + 115,638 - 12 = 3556,935 + 579,74 - 12 =
= 4124,67 = 4,2 • IO3.
д) Выбираем
r} = 31 • 89 = 2759, r2 = 3191, r3= 23 - 881 = 20263, r4= 201961;
2(7Г1 +7ъ+7'Г + 7^7+6 ,Og2 'ir2r3r4 + 610Й2 rlr2r3 + 6 ,Og rir2 +
+ 21og2 rx - 17 = 1401,527... + 715,535... -17 = 2100,06 ...« 2,1 -103.
6.2. a)/-l «2,2 • 109.
6) 2(7? + log2 0 = 2l6</2 + 32 =9,3 • 104.
68
Глава 7.
ЛИНЕЙНЫЕ
РЕКУРРЕНТНЫЕ
ПОСЛЕДОВАТЕЛЬНОСТИ
КАК ПСЕВДОСЛУЧАЙНЫЕ
ПОСЛЕДОВАТЕЛЬНОСТИ
§1, ЧИСЛО ПОЯВЛЕНИЙ НАБОРОВ ФИКСИРОВАННЫХ
ЗНАКОВ НА ПОЛНОМ ПЕРИОДЕ МАКСИМАЛЬНОЙ
ЛИНЕЙНОЙ рекуррентной последовательности
Используем следующие обозначения главы 5
n ~ n- 1 "+••• Т » (7*1)
/ = /(М = А,и-«1Г1~
характеристический многочлен рекуррентного уравнения (7 1)
Далее заметим, что для любых элементов 8Х(л, 8Х+Я_1, • из
поля Fp уравнение (7.1) разрешимо. так как ап *0 В соответствии с этим
под решением здесь будем понимать двустороннюю последовательность
о “ = элементов потя Ff, удовлетворяющую уравнению (7.1).
Нетрудно видеть, 1гто любой сдвиг тк, где к е Z, двусторонней последо-
вггсльности 8 = {ov}v переводит последовательность 8 = [5V}V в себя. Поэтому в
качестве начальных значении последовагсльносли 5 можно выбирать любой на-
бор последовательных значений послстовательности 8. Термины - минимальный
многочлен решения- главное решение, примитивный период решения - могут ис-
пользоваться и при новом расширенном понимании понятия ' решение линейного
рекуррентного уравнения". Следующие результаты главы 5 верны и при данном
пись истолковании понятия "решение линейного рекуррентного уравнения",
всякое решение б уравнения (7.1) периодично и его примитивный период
per 6 р ’ - С а также что
1) per 8. = ord ср,
। де ф = ф(Х) - минимальным многочлен решения 8;
2) per б = ord f,
69
где 8 - главное решение уравнения (7 1).
Теорема 7.1. Пусть f- примитивный многочлен над полем Fp степени к
8 - ненулевое решение уравнения (7.1); t = ord / = per 8 =р”- 1; s, ти т2,mt
натуральные числа с условиями 1 <, s £ п; 0 £ тх < т2 <... < m, < t; Ьь Ь,
элементы поля Fp; Tt = Tt(bb by b„- mb m2, ...» ms) - число решений
целых числах х системы уравнений:
°х+/я1
»х + т1
- Л,,
-
V 4 wt ♦
Тогда
где £
Р
Р
1
„ж
Доказательство. Так как примитивный период максимальной линей
ной рекуррентной последовательности равен t = рп - 1, то каждый йену лево
набор п элементов поля Fp встречается и только один раз на примитивном
периоде этой последовательности. Поэтому число ненулевых комплексов
(наборов) длины п, на каких-нибудь s (s < w) отмеченных местах которых
стоят фиксированные элементы, равно.
a) pn s у если на отмеченных местах стоят нс все нули;
б) рп $- 1, если отмеченные места заняты нулями. □
§2. Свойства решений линейного
РЕКУРРЕНТНОГО УРАВНЕНИЙ
Обозначения. Г„- «-мерное векторное пространство над полем Fp; О
нулевой вектор пространства а • 0 - скалярное произведение векторов а
и р пространства К,; х ~ характер аддитивной группы поля F^,; х0 - глав
ный характер аддитивной группы поля F^.
Для каждого j е {0, 1, ...,
п - 1} р(у) = - решение уравнения
(7.1) с начальными значениями: ру>
70
р?-,)
- матрица рекуррентного
О 1
о о
о о
о
о
1
\ равнения (7.1),
В = Аг - матрица, транспонированная с матрицей А.
Легко проверить, что
। с. столбцами матрицы В являются векторы 02,;
h(/), 0^ j<k - все различные решения уравнения (7.1), такие, что ни одно
из них не может быть получено сдвигом из другого; их множество условимся
обозначать символом L(f), таким образом, L(f)~ |б<7)| 0 < j < /с};
(7.2)
Теорема 7.2. Множество векторов {a^I 0 < у £ 0 £ х < } -
суть множество всех векторов пространства Уп.
Доказательство. Очевидно. □
Теорема 7.3.
а) Ух е Z А • Ах= Ах+б
б) Vx 6 Z Ах• Ао= Ах.
Доказательство.
а) следует непосредственно из равенства (7.1);
б) следует из а). □
Теорема 7.4. Vx е Z, Vy е Z
8Х+, = 8Х0) +8,мР?’ + •••+»,—•₽? “• <7-3)
Доказательство. Равенство (7.3) верно при х = 0, х = 1,..., х = и - 1
при фиксированном у, таким образом, решения 5^ и • А, равны при п по-
следовательных значениях переменного х, следовательно, они равны. □
71
Теорема 7.5.
а) V х е Z В • рх. = р^;
6)VxeZ Вх.р0=рх. 1
Доказательство. В равенстве (7 3) полагаем у = 1 и заменяем 8Л на р*А):
Р<‘Л = Р.<‘,Р10> +р!‘)р',’+...+Р<‘’р'“-1>. (7.4)
В равенстве (7.4) полагаем последовательно к = 0, к = 1,...»к = п - 1:
р‘°Л = рГ’рГ’ +рГ’р1,)+...+ р<”р? ’,
р<Л,. = р<1,,р’0,+р<2,,р^+...+р">рГ,).
рК? = р!" ‘W» +pi" ,,р1+...+р!."-,>р£"-,>.
Тем самым равенство а) доказано. Из равенства а) следует б). □
Теорема 7.6.
Vx g Z рл-+я- «1 Рх+л-i + ••• 4- а„рх.
Доказательство. Легко следует из равенства (7.1) и теоремы 7.4. О
Теорема 7.7.
а) Если 6- главное решение уравнения (7.1), то для любого х с Z
векторы Д„ Д^,..., Дч^„^1 линейно независимы над полем Fp;
б) для любого х е Z векторы ри р^,..., P^+^-i линейно независимы над
полем Fp
Доказательство.
а) В самом деле, если существуют не все равные нулю элементы с2,
такие, что
<лДх+ с2Дх+1 +... Д.к+л-1 = 0, (7.5)
то, умножая обе части равенства (7.5) слева на А~\ из теоремы 7.3 получим
с1А-0+ c2Al+ ... +ся_1Дя_1 - О,
что не может быть, так как в изоморфном отображении т пространства S(f) на
F,u базису’ < 5, Т • 8,7* «8,..., Г*-1 • 8 > отвечает набор < До, Дь...»Д„-1 >. □
б) Легко выводится из теорем 7.3 и 7 4 □
Теорема 7.8. per р = /.
Доказательство. Так как примитивный период главного решения
уравнения (7.1) равен t , а главное решение - базис пространства S(f), то
Vx е Z 8лЧ7 = 8Х
для любого решения 8 уравнения (7 1). Следовательно,
Vx с Z рА^ =
С другой стороны, если
Vx е Z р^ = р„
то
72
\/x e z p!?.’ - p!7)
i in каждого j от 0 до n - 1, и в частности, для j = и - 1. А так как р("п-
। ii.'iBHOC решение уравнения (7 1), то nt > t. □
§3. Суммы с характерами
Теорема 7.9. Пусть X=Xq- группа характеров аддитивной группы
поля F-Fq; X- характер группы X; Хо- главный характер группы X.
Г ел и X Хо» с~ элемент поля F, то
£хО) =
eeF
q О с = О,
О <г> с Ф 0.
Доказательство. Если с * 0, то вместе с а произведение ас пробегает
нее множество элементов поля F. См. также теорему Д. 7.2. Г ]
Теорема 7.10. Пусть X=Xq - группа характеров аддитивной груп-
пы поля F = Fq; % - характер группы X; Хо - главный характер группы X.
Если X ^Хо» то
Я| ,a2,...,ak сЕ
+ a2c2 + ... + akck) =
< qh =c2 = ... = ck =0;
0 Cj с2 . у ck > < О, 0,
0>.
Цругими словами,
X Х(а*Т) =
а с Г„
0 <=> у & 0.
Доказательство. В самом деле.
£х(¥1+¥2 + --Нс*)=£ Х(Й1С1) ’£х(«2<9* •••• ExKcJ-
л,,а2,...,акеГ a‘tF а2 gF akcE
Из теоремы 7.9 и следует наше утверждение. □
Теорема 7.11. Пусть X=Xq - группа характеров аддитивной груп-
пы поляр ~ Fy Х“ характер группы X; Хо - главный характер группы X. Ес-
т х *Хо > 7 е м “ множество ненулевых векторов пространства У„ ,
то
V { \ 1 <=> у = 0;
(1 G 1
Доказательство. Следует из теоремы 7 10. О
73
Теорема 7.12. Пусть a cZ. Тогда
г
Х=1
t <^> а = 0 (tnodf),
О <г> а Ф 0 (mod Г).
Доказательство. В самом деле, функция et(ax) - характер аддитивной
группы кольца классов вычетов по модулю t. □
Обозначение: f - характеристический многочлен уравнения (7.1),
r = ord/- 5 - какое-нибудь решение этого уравнения; 6<0), ..., —
все, с точностью до сдвига, решения уравнения (7.1);
£(/) = {б((,),8,,,,...,8(‘>} - множество этих решений; у - неглавный харак-
тер аддитивной группы поля F- Fq, у а~ целое число, N - натуральное
число;
N
°a,N (S) = £ %(8Х) • eN (ок);
х=1
j = 0,1,..., Л;
(8) = cto.n (8) = £ Х(6 ж);
Х=1
регб
a(8)=Sx(8,)-
хМ
Легко проверить, что
сто,/(6) = —ёа(8)-
рего
Теорема 7.13.
к
1
(7.6)
2) У
Sc7(7)I’er8
Доказательство. Для любого у е Z
откуда
t
xl
74
Но в сил} (7.3)
Огсюда, используя теорему 7.2, получаем
* 2 Г 2
хУ, 1стУ I= Е ЕхФ*>а)вА««) =
j = o аеКв Х=1
У, xftPx-₽«)•“)•
х=1г-1 аеКм
Заметим, что рег0 = t. Поэтому
£ £ et (а(х - г)) £ х((₽х - ₽г) • «0 = >Р "
X=lz=i асКм
Итак,
J=o
В частности, при а = 0 легко получим
Беге/) Рег^
2 1
1 а(5) 1 °
ord/
§4. Максимальные линейные
РЕКУРРЕНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ КАК
ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ
Обозначения. 8 —главное решение уравнения (7.1); у-ненулевой
вектор пространства К; ух= Вх • у;
стд,г(й) = сгв><(8,у) = £%(у • AJ et(ох).
X—I
Теорема 7.14. Пусть f - примитивный многочлен степени п, а е Z,
<}<, a <t; тогда
п
р2 <=> 1 а <
1 о а = 0.
ь
Доказательство. Так как t = р*- 1 - период любого решения уравне-
ния (7 1), то для любого целого у
75
£ %(y • A J et(ax) - £ z(y • Д* + p))
Далее заметим, что
Y • Ax+> = 7 x • Дj,.
Поэтому
•AJr) •<?,(«*)
Следовательно,
‘ Ю..Г (5; V)| = X E E X«Y « - Г « ) • A, ) e, (a(x - z)) =
J' lx lz = l
* t t
= E E e> ("")E X«r«„ - Ъ ) • A ,) =
M=lz=l >-1
= z?’'^ХО’) + ЕЁ<-',(шО- Ех«Ъ+г-Гг)«а) =
i — 1 T-l u = l 2= 1
z 1 a с I'
Таким образом.
„-„с is n \ 7 " многочлен над полем
Y e К» у * 0 ; Л - натуральное число,
'р сте-
N
CT.^)=Xx(y ,AJ-
X 1
1.СЛК 1 <. N < t, mo
|a(^)( - |стд- (fi)| £ p 2 In/.
Доказательство. Имеем
/V t t
S S X(Y * А*)е'(а(л “ г)) = Ё Ё X(r • Ax >Ё e,(“(x - Z)\.
a-1 *=1 X=1
Обозначая левую часть тождества (7.7) символом А, получим
(7.7)
76
,V r t Л’
г-1 л 1 а=1 х=1
I'.вбивая правую часть В тождества (7.7) на два слагаемых, получаем:
t r-l t N
в = х(У • ДЛ) + ^ 52 Х(у • Лл)52 =
х—1 «=1х=1 г=1
t 1 t N
=-^+52Хх(уеДхХм52£7( «)•
a=lx I г 1
< )1ьюда следует, что
л 1
.V
Х‘'<(_аг)
г-н
Воспользовавшись теоремами 7.14 и Д. 7.7, находим
ЛГ
»/-1
|В|^Л + p’Y
а
5^g/(-gz) <N + p2(/ln/ ——) <tp2 In/.
Z=1 2
Из тождества (7.7) получим объявленный результат. IJ
Теорема 7.16. Пусть f - примитивный многочлен над полем Fp степени
п; 5- ненулевое решение уравнения (7.1): t= ord f= perS =p"-l; x, mbm2t...» mx -
натуральные числа с условиями 1 <s <п; О <nti< т2 <... < mt < t; Ьь Ъъ ..., bs -
элементы поля Fp; N- натуральное число с условием 1 < N < t\
1\~ TN (Ль Ьг^ ..., Л,; шь ш2,..., mJ - число решений в целых числах х сис-
темы уравнений
^х + ги, — ^1 ’
^х + /п2 ~ ^2*
........
l^x</V.
Если рж — линейно независимы над полем Fp, то
N ~ II
Tv= — + ер2 !п/, где | с | < 1.
р‘
Докаппельсгво. Имеем в силу' теоремы 7 10:
77
1 N
~ P' C c.F “*1)+•••+Cs’(5je+m -Л4)) =
r ul«” Iе, btf X=1 »
1
p*
£x( СЛ-—-^A) Xx(y*Ax),
где
f X(q8^„| + .+c,8„„) = z((C1 pm_ +C2p^ +.„+c>pm<).Aj
Ho
с1₽/я) + =6<=>q = ... = c, =0.
Поэтому
rp _ TV 1 Й N
N~V+V ^-сЛ---^А)Ех(г*Аж).
где £ ” _
ci’eF,
сумма по всем ненулевым комплектам <cu..., Cl
Отсюда и из теоремы 7.15
и следует наше утверждение. □
Vn ебраическое
пополнение I.
Конечные группы.
Теорема Лагранжа
Д. 3.1. Определение. Число элементов конечной группы называют ее
порядком. Порядком Элементу g группы G = < G. *, е > называют наи-
м< нынее натуральное число п с условием
=е-
Д. 3.2. Теорема Лагранжа.
(1) Если т - порядок группы G = <G, *,е > g - элемент группы G. то
ёГ=е.
(2) Если п - порядок элемента g группы < G,*, е>, т е N, то
g^‘= е <=> /и = 0 (mod и).
Доказательство. (1). Если gi, g2,..., gm - все элементы группы G, g -
•цемент группы G, то g • gu g • g2, ..., g • g„t - также все элементы той же
। руппы. Поэтому
g • £1 • g • gl ’ ... • g gm=gl • gl ... • gmt
отсюда легко выводится первое утверждение. □
(2) . Если т = п • q + г, то
Мои доказывает второе утверждение, □
Л п 'сбраическое
дополнение И.
Простое расширение
поля. Поле разложения
многочлена
Д. 3.3. Определение. Пусть F- подполе поля Н; 0 е Я. Минимальное
поле, содержащее поле Fh элемент 0, называют простым расширением по-
ни F, полученным путем присоединения к полю F элемента 0.
Обозначение. F(0) - простое расширение поля F, полученное путем
присоединения к полю F элемента 0
Д. 3.4. Определение. Пусть F - подполе поля Н; f - многочлен над
полем F; 0 - корень многочлена f в поле Н. Тогда простое расширение F(0)
называют простым алгебраическим расширением, полученным путем при-
79
соединения к полю F корня 0 многочлена f. Если многочлен f - неприводи-
мый над полем F степени п многочлен, то расширение F(0) называют про-
стым алгебраическим расширением поля F степени п.
Пример. Поле С комплексных чисел является простым алгебраиче-
ским расширением степени 2 над R, так как поле комплексных чисел получа-
ется присоединением к полю действительных чисел многочлена х2 + 1 над R.
Д. 3.5. Теорема. Пусть F- подполе поля//, /- неприводимый степени
п > 0 многочлен над полем F с корнем 0 в поле Н. Тогда любой элемент
поля F(0) однозначно представим в виде
w = «о + «1 - 0 + аг • О2 +.... + а^ • О"-1, (Д. 3.1)
где ап,an_i — элементы поля F
Доказательство. Докажем сначала, что представление элемента w в
форме (Д. 3.1) однозначно В самом деле, предположив противное, получим ра-
венство
«„ - Ьо + (в, - Л, )0 + (а, - аде2 + = о,
из которого будет следовать, что неприводимый многочлен степени п и мно-
гочлен £г0- ba + (а, - b 1)0 + (аг - Ь2)02 +... + (апА - Ь„л)0" 1 имеют общий
корень. Остается доказать, что множество АДО) всех выражений вида (Д 3.1)
относительно сложения и умножения образует поле Дтя этого достаточно
проверить, что а) сумма, разность и произведение элементов из Л/(0) принад-
лежит М(0); б) элемент, обратный ненулевому элементу из А/(0), принадлежит
Л/(0). Проверим б). Пусть »е(х) е 4/(0) и »f(x) - ненулевой многочлен. Тогда
и’(х) и/(х) взаимно просты. Поэтому можно найти многочлены н(х) и v(x)
над полем F такие, что
и<х)«(х) +/(х) v(х) = 1 (Д. 3.2)
и deg и(х) < п Полагая в равенстве (Д 3.2) х = 0, получим н^О)”1 = и(0), сле-
довательно. и-(0) е 4/(0). □
Поле разложения
Д. 3.6. Определение. Пусть F- поле. /- многочлен над полем F.
Полем разложения многочлена f над полем F называют минималь-
ное расширение Н поля F, в котором многочлен f разлагается в произведение
линейных над полем Н многочленов.
Д. 3.7. Теорема. Пусть F - поле и f -многочлен над полем F. Тогда
(1) существует поле разложения многочлена f над полем F;
(2) любые поля разложения многочлена f над полем F изоморфны.
Доказательство.
(1) Пусть / - неприводимый многочлен над полем F. Рассмотрим
кольцо Н классов вычетов кольца многочленов над полем Fno модулю/, т.с.
кольцо Н = FJxJ/^. Каждый элемент кольца Н можно рассматривать как
80
множество многочленов над кольцом F вида g +/х w, где w е Fjx| и g - не-
ннорый фиксированный многочлен, в частности, элемент поля F, Многочле-
•Н1 и и v принадлежат одному классу кольца Н, если их разность и - v депт-
1 на f В кольце Н класс (Г)/=(О)/=о является нулем Кольцо Н является
пнчем и расширением поля F, более точно, кольцо Н содержит подполе, изо-
морфное полю F. А именно, отображение
Х/а е F а -> (a)z
определяет изоморфный образ поля Fb поле Н. В самом деле,
Va е F& Xfb е F а = Ь о (a)z= (Ь)^
а + b -> (а + A)z= (a)z+ (/>)/
а х b -> (а х b)j= (a)zx (Ь)?
Обозначил! символом х неизвестное (переменное) для многочленов над
। ольцом Н. Многочлен f над полем Н можно записать так:
f =fix) = а0 + <hx + а2 х1 +... + апх я, (Д. 3.3)
•HIM
/ = fix) = (a0)z + (ai)fx +... + (a„)z x n.
I Io лагая в равенстве (Д. 3.3) х = (x)z е Я, получим
= (<*о + ai х + а2х2 + ... + апх {f)f- (0)z = 0.
Таким образом, многочлен f в расширении Н поля F имеет корень.
I ли среди неприводимых над полем Н делителей многочлена f имеются
v лители выше первой степени, то так можно продолжать дальше. В резуль-
| .1 re найдем такое расширение Рполя F, в котором многочлен f разлагается
и произведение линейных множителей.
(2). Ограничимся изложением идеи доказательства. Пусть F- поле и
/ неприводимый многочлен над полем F. Н и W- расширения поля Fтакие,
н которых многочлен f имеет корни 0 и со соответственно. Тогда расширения
Л(0) и F(w) изоморфны. В самом деле, каждое из них изоморфно фактор-
I о 1ьцу Отсюда следует, что теорема Д. 3.7 доказана для случая когда
многочлен /неприводим и над полем F(G) многочлен f разлагается в произ-
ведение линейных множителей. □
Пример. Поля разложения многочленах2 + 1 над полем рациональных
чисел и над полем действительных чисел нс изоморфны.
4-364
81
Алгебраическое
дополнение ш. Конечное расширение
Д. 3.8. Определение. Пусть F,H- поля и Н - расширение поля F. Поле Н
называют конечным расширением поля F, если поле Н содержит элементы
Л1, Л2 >-м Л*, (Д. 3.4)
такие, что любой элемент h из Я линейно над полем F выражается через эле-
менты (Д 3.4), другими словами, уравнение
h = hx • jq 4- h2 • x2 +... + hk • xk
(Д. 3.5)
разрешимо в элементах хь х2,..., хк из поля F. Если уравнение (Д. 3.5) имеет
единственное решение в элементах из поля F для любого Л поля Н, то набор
элементов (Д. 3.4) называют базисом поля Н относительно поля F.
Число к в этом случае называют степенью конечного расширения поля
Н относительно поля F.
Обозначение. (Я.*!5] - степень конечного расширения поля Н относи-
тельно поля F.
Пример. Поле С комплексных чисел является конечным расширением
степени 2 поля R действительных чисел, так как каждое комплексное число
есть число вида а • 1 4- А • ь
Д. 3.9. Теорема. Всякое простое алгебраическое расширение поля F
степени п является конечным расширением поля F степени п.
Доказательство. Следует из теоремы Д. 3.5. □
Д. 3.10. Теорема. Если поле Н конечно, F- его подполе, то Н — конеч-
ное расширение поля F.
Доказательство. Очевидно. □
Д. 3.11. Теорема. Если поле Н - конечное расширение степени п поля
F, то любые л + 1 элементов поля Н линейно зависимы над полем F.
Доказательство. Пусть Л2,..., hn- базис поля Н относительно поля
F и и’о, w2,...» пя- какие-нибудь элементы поля Н. Тогда в поле F сущест-
вуют элементыa,j, 0 < i^n ,1 <, j<,n ,такие, что
.................................... (Д. 3.6)
и’„= anXhx 4-... +annhn.
Если в прямоугольной матрице число строк больше числа столбцов, то
ее строки линейно зависимы. Поэтому из равенств (Д. 3.6) следует, что эле-
менты »v0, и’2,..., w„ линейно зависимы над полем F.
Контрпример. Поле R действительных чисел не является конечным
расширением поля Q рациональных чисел. В самом деле, для любого нату-
82
р.ыьного п можно указать неприводимый над полем Q многочлен степени п,
к следовательно, и набор из п линейно независимых над полем Q элементов. □
Д. 3.12. Теорема (о степени конечного расширения). Пусть F, Н, W-
поля. Тогда
(1). Если Н - конечное расширение поля W, а поле W - конечное рас-
ширение поля F, то Н-конечноерасширение поля Fи при этом
[Я.-FJ = [H:W\ • \W:F\. (Д. 3.7)
(2). Если Н - конечное расширение поля F, a W - промежуточное по-
чг, т. е. Fa Wс Н, то Н - конечное расширение поля W, a W- конечное
расширение поля F и при этом выполняется равенство (Д. 3.7).
Доказательства Предположим, что < hi,...» ЛЛ > базис поля Н относи-
юльно IV, а < и»,..., >vm> базис поля Wотносительно поля F. Легко проверить,что
Л, • wj| i = 1,..., k; j = 1,m > базис поля H относительно поля F. □
Арифметическое
, юполнение I.
Принцип обращения
Мёбиуса
Д. 4.1. Определение. Функция Мёбиуса.
1,-1},
• Pi ’ ••• • Рл)=(-1)*> если pt, ...,pk - различные простые числа,
ц(р2 • п) = 0, если р - простое число, п - натуральное число.
Д. 4.2. Таблица значений функции Мёбиуса (1 п <. 30)
п 1 : 2 | 3 5 6 7 i 8? 9 io i и 1 12 i 13 j 14 ? 15
\*(") 1 i -1 ! -1 о! -1 1 -1 ! 0 j 0 i i -1 1 °! -1 i 1 j 1
л 16 i • 17 : 18 ? 19 j 20 i 21 i 22 ? 23 i 24 j 25 i 26 j 27 i 28 j • 29 i 30
iW 0 = -1 i 0; -1 j °; 1 = 1 ; -I 5 °; 1 : °; 0 j -i i -i
Д. 4.3. Теорема. Если натуральные числа тик взаимно просты, то
• к) = |л(/н) • р(А).
Доказательство. Очевидно. □
Д. 4.4. Теорема.
X Н("0 =
1 о п = 1,
О <=> и > 1.
83
Доказательство. Будем предполагать, что п > 1 и р - простой дели-
тель числа п. Таким образом, п = р к. Тогда
X н("0 = £ иО) + £ p(jW») = (1 + Ц(р))£ р(ш) = о. □ I
л»|л т|А ж|А ж]А
Д. 4.5. Теорема (принцип обращения Мёбиуса). Пусть fug - ариф-
метические функции, удовлетворяющие условию:
2Lg(w) = f(n). (Д. 4.1)
т|л
Тогда
52н(^)/(—)=g(«)-
т|И т
ЛП1Л
Наоборот, если верно (Д. 4.2). то верно и (Д. 4.1).
Доказательство. Пусть т, k, I- натуральные числа такие, что
т • к • 1 — п. (Д. 4.3)
Обозначим символами а, сг(|И), а(А) суммы вида
<к,т> к т
такие, что в первой из них суммирование происходит по всем парам нату-
ральных чисел < А, т > с условием (Д 4.3), во второй из них суммирование про-
исходит при фиксированном т по всем натуральным к с условием (Д. 4.3), в
третьей из них суммирование происходит при фиксированном натуральном к
по всем натуральным т с условием (Д 4.3). Легко видеть, что
о = Ха<-> =
л«<л А]л
а также, что
С(т)= Х/(*)ц(т), с<‘>= £/(*)ц(т).
А|л/ж л<|л/А
Таким образом,
л»(лА|л/л» А|л ж|л/А
или
52 ц(™) 52 /(*)=£/(*) £л("0-
Ж]Л А]л/л1 А|л л>(л/А
Из теоремы Д. 4.4 и равенства (Д 4.1) следует равенство (Д. 4.2). □
84
A| »i кинетическое
дополнение II.
Характеры конечной
группы
Определение. Пусть G = < G; •> е > - конечная группа, число элемен-
тов которой п больше 1; комплекснозначную функцию х из G в С называют
* арактером группы G, если она удовлетворяет следующим условиям:
1) Ча, b е G %(а • &) = х(а) - хФ);
2) х(е) = 1.
Нели
3)VecG x(«) = h
•о характер х называют главным характером группы G и обозначают Хо(л).
11 противном случае характер х называют неглавным характером группы G.
I ели в качестве группы G рассматривать аддитивную группу поля, то
X (« + />) = х(а). х(^) (7.1)
urn любых элементов а и b поля F^K и
X (с) * 0 (7.2)
д.ия какого-нибудь элемента с поля F?.;
Хо (") = 1
тля любого элемента а поля F?,..
Д. 7.2. Теорема. Пусть X — Xq - группа характеров аддитивной группы
no.nHF-F^ х- характер группы X; Хо - главный характер группы X. Тогда
я <=>х = хо;
О <=>Х* Xu-
Д. 7.2. Пример. Пусть G - < G; •, е> - конечная циклическая группа
порядка п и g - примитивный элемент группы G. Тогда
все элементы группы G Пусть е - какой-нибудь корень степени п из 1 Если
а = g* для неотрицательного целого к, то полагаем
Х(«) = Х(/) = с*.
11етрудно проверить, что х - характер группы G.
Д. 7.3. Пример. Пусть G = < G; »,е>- конечная коммутативная груп-
па порядка п; < gu ..., gk > - базис группы G, причем элементы gu g2i...»gk
порядков «1, w2, ..., пк соответственно. В этом случае любой элемент а е G
однозначно представим в виде
85
а = 2 — g?; 0 < xi < л,; 0 < и2;О < хк < пк.
Пусть далее ct, е2, ..., еЛ - комплексные числа такие, что
е? = 1,е”2 = 1,...,eJ”* = 1.
Полагаем
X(e)= ер-ef - e,*. (7.3)
Легко проверить, что функция
определяемая равенством (7.3), есть характер группы С, а также чго каждый
характер группы G может быть таким образом определен. Таким образом, чис-
ло характеров группы G равно пх • п2... мк = п.
Д. 7.4. Пример. Обозначим е,(х) = ехр (2тп у).
Легко видеть, что
1) для любого а е Z et(a(x +.v))= et(ax) • et(ay),
2) для любого a g Z et(ax) * О,
3) для любого а е Z, если х s у (mod Г), то et(ax) = et(ay).
Поэтому et(ax) - характер на аддитивной группе классов вычетов по модулю t
Д. 7.5. Пример. Пусть G = < G, +, 0 > аддитивная группа конечного
поля . Так как поле/у, есть конечное расширение степени п поля Fp, то
оно содержит базис < f\,f2i..., f„> относительно поля Fp. Любой элемент а
поля F^ однозначно представляется в виде
a = xifi+x2f2+... +xnf„,
где Xi, х2,..., хп - элементы поля Fp. Характеристика поля F}>n равна р. По-
этому порядок каждого ненулевого элемента группы G = < G, +, 0 > равен р.
Для каждого а е F^ определим х равенством
2 я-1
а+ар + ар +...+ар
2ni------------------
х(«) = е р
Из сказанного выше легко получить, что х - характер группы G.
Д. 7.6. Теорема. Пусть G — < G; •, е > коммутативная группа и %-
неглавный характер группы G. Тогда
Ех(*) = о.
bt=G
86
Доказательство. Пусть с - элемент группы G, такой, что х(с) * 1.
11мсем
£х(*) = £х(М-
b^G bhG
< )тсюда получим
(»-xW)£x(*) = o-d
beG
Д. 7.7. Теорема. Для любых натуральных t > 12 и N:
а~1
z=i
Доказательство. [8], гл. 3, вопрос Ис. □
Д. 7.8. Теорема. Для любых натуральных t и N
t-i
I
N
г=1
2 2
<-f ln/ + -f + 7V.
71 5
Доказательство. [27], лемма 8.80. □
ПРИЛОЖЕНИЯ
Приложение 1.1
Морзе азбука (русский вариант)
А._ Б_... В__ Г__ Д_.. Е. Ж..._ 3__.. И.. й.___
К___Л_ М__н_. О____ П._. Р._. С... Т_ у__
Ф.._. х.... Ц__ ч____ш______Щ__._ Ы_.__ Ъ;Ь___ Э___ Ю___
Я___
1_____ 2________ 3________ 4_______ 5... 6____
7--- 8---------- 9-------- 0_________ М ....... [,]______
(:]----- (;]----- [!]------ [()]-----------------
[/1--- 14------- (нп|_------
нп - "начало передачи" кп - "конец передачи"
Приложение 1.2
Русский алфавит
1)А 2)Б 3)В 4)Г 5)Д 6)Е 7)Ё 8) Ж 9)3 10) И 11) Й
12) К 13) Л 14) М 15) Н 16)0 17) П 18) Р 19) С 20) Т 21) У 22) Ф
23) X 24) Ц 26) Ч 26) Ш 27) Щ 28) Ъ 29) Ы 30) Ь 31)3 32) Ю 33) Я
88
Приложение 1.3
Цифирь Петра I для П.А. Толстого
А Б В р Д Е Ж 3 И К л
ме ли ко ин зе жу ню о ИМ ра су
М Н О п Р С Т У Ф X ц
ти У хи от ца чу ше ам 3 ъ от
Ч Ш щ Ъ Ы Ь Э Ю Я
ь ю я Ф а бе за *У ди
Приложение 1.4
Таблица относительных частот (о. ч.)
встречаемости букв (б.) в русском тексте
(Доля числа буке на 1000 буке текста)
б. о.ч б. о.ч б. о.ч б. о.ч
а 0,062 и 0,062 Р 0,040 ш 0,006
б 0,014 й 0,010 с 0,045 0,003
8 0,038 к 0,028 т 0,053 ы 0,016
г 0,013 л 0,035 У 0,021 ь; ъ 0,014
д 0,025 м 0,026 Ф 0,002 э 0,003
е; ё 0,072 н 0,053 X 0,009 ю 0,006
ж 0,007 о 0,090 Ц 0,004 я 0,018
3 0,016 п 0,023 ч 0,012
89
Приложение / 5
Расположение букв русского алфавита
по их относительной частоте
1)0 2) е; ё 3) а; и 4) н; т 5) с 6)р 7) в
8) л 9) к 10) м 11)Д 12) п 13) у 14) я
15) ы; з 16) ь,ъ 17) г 18) ч 19) й 20) х 21) ж
22) ш; ю 23) ц 24) щ; э 25) ф
Приложение 1.6
Греческий алфавит
А, а Альфа в,р Бета Г, у Гамма А, б Дельта Е, е Эпсилон
н,п e,s К, к
Зета Эта Тэта Иота Каппа
ЛА М,ц N, v [I] О, о
Ламбда Ми (мю) Ни (ню) Кси Омикрон
П, 71 лРЕ, ст Т,т Y,u
Пи Ро Сигма Тау Ипсилон
ф,<р х,х Q, сй
Фи Хи Пси Омега
90
Приложение 1.7
Таблица Виженера
Л! Б j В= Г = Д: Е= Ж: 3 j И
I 1 | V* • В а • аеваааа Л а. i .а • а а а «а а в о Ма а а МВ а а а а
«; Г : Д: Ei Ж: 3 i Hi Й i К:
.а аЧ ааа a Faa aeiK a a a a Fa а аааЧ а а a a Fa аа а Аа. а «Лев а аЧ
Г: Д': Ei Ж: 3 Ё ИЙ: К i Л:
Д: F.: Ж; 3: И: И: К: Л : М:
I.: Ж? 3: И: Й= Ki Л: Mi Hi
К] Л: h|.H[Oi
<].и1.й1.к> ..-Л .Л?1.9.1.и1
Ы.01л1л.1м..|.1.1р1д1г1
.Ш.кШ.Ши.21п;.р i cj
к] я[м: Hi oi ni pjcjT i
л i Mi н; oi ni pi ci Ti yi
...-a.>...{...J... •(.... фа...фа.aa)
Mi Hi Oi П: Pi Ci Ti У: Ф:
к.: л j m;
nj wi II;
м? н i о i
.................:
H i О: П :
афааааСааааа]
Oi П;P i
---«J---a.%aa.aa4
ni p i ci
Р j С; Т
С • Т У
nipiciT yi ф: xi ui ч: iif uji ь
I a a » {a a a aaja aa aa^l a a aa{ a a aaa^ aaaa J a aaa ф a a al g aaa a a^ aaaa • a^a a a • I
P i Ci T: У Ф: Xi Hi 4: Ilf Ilf b i Ы
.4................................>. -Y..
У'i’ Ф- xi ц: ч! щ' 14 b i ыТэi Ki я”
। ааа «аааааааааа aiva a al а«ае а а а ааа а а а а еа»а а а а<м a a a a wa a aaaa в aeai
Фi xi qi 4i ui ui bi bii si Ki я. a
l aa a«a aaa aa aaaa М» aaa a a aaaa ^aa a aVaae a aaaa aaaaaaaa a«a a a a«aa aaaB a III
Ы: 3 i КЗ Я : A
—••[ J—a.I
Э: Ю Я: А: Б
>....{.....>—
.К^.Я : А: Б : В
я] aJ bJ в Ё г
.аГбТёГгГд
А: Б
Bi В
.ЦД.
Xi
Е; Ж
Ж; 3
ni p! ci Ti у] ф; xiцТч
• •aaavaaa iviaaa a a a«a a a a* a aaaaaaaa ем aaal aaa aaaa
£111.У1Ф.х1Цк51.?Ц1.Ц£
фё xi ц ч: iii iir ьi ui si id ni Ai в i Bi г
» - * "J a a afaa a aajaa aafaaaaa* a a a.J^ a.a-far --«}> • •.}ааавфв.ав[вввва}аавв{вева a J—a a a
Xi II: 4 i Ilf HE b i Hi 3i KJ Я
a.a a>.a al{ a a a a .) a a a a 4. a a a a^....-J aa.a>a...J.a...
.ЙМШ
b.i.bilЭ; id я i а| вj в
Ц£ ь].ьн.э[ю hJ а#[б£в[г.
Oi X: Ц: Ч: Uf П5 Ь: Ы: 3:
. ..фа. а.{а.а.а).а.а..а.фа...{.а. в.)
ч[ ui iii ь! bii si id я Та;
в аа a a*aaaa«a ааааф a a a a«a а.емааа.аааа.мвеаа маа.аа
ini щ bi ы; oi id я? Ai б i
a..«••••II a a* a a a aaaa a a aaaa ........ Ml aaaa Ml . ... a
Я : А : Б : В : Г :
а а а V*» а а >а» а а а,, а а а ^а* в a aj
Ai в i Bi Пд;
кТв[г’ГдГё;
Bi.r [Д i.E i ж;
Ь.ЫлЭдКЗ Я : А БBj Г
ui з i id я i a i ь i вг | д
3 i Ю Я i Ai Б i В i Г . Д i Е
F.i ж.= з i и; й =
а а афа а аа{аа а аа«»^ва«ва|
Ж: 3 : И: Й: К:
....
3 • И; Й: К: Л;
....... . . ¥“'a»'«a,a**,”V,4,<
Я? A; Bi Bi Г : Д= Е= Ж:: 3 : Hi Й; К- Л= М:
jdj.i.wlftj k
зГЁй fijKi л
Hj iii Kj iij m.
ftl.Ki. л£кё ii
к; л; mFni о
Л1 Mi Hi Oi п
... о фа...;., a. a>a...
M[.H: OjHi P
hT oi ni P i C
Ai Б i В: Г: Д
Б = Bj fJ Д: Е,
Bj И ft! Ei Ж
Г = fl! Ei Ж; 3*
aaaaaaaa «а«ава»«а ааааа aaa»i
,E:.^i, 3 i и ; Й
ii(i з i и f й i к
aaa a{aaaaаЧ aaa aFaaa а аЧааа a 4
з i и i й i к i л
— ....5-—
И i Й i К i Л : M
..-.(a.-.........
Й К : Л i M: H
к i л i Mi н i o
Д: E Ж 3 i И
aaa\{aa a a a^aaafaaaaa^aaaa
E: Ж! 3 i Hi Й
Ж=.3 : И
з i и; й
и: й]к
,й[к] л
Ki л; м= н; о
Л: М: Н: О* II
М: Н : О: П • Р
Н: О: П: Р : С
Oi П:PiС: T
П! P i Ci Ti У
a aaaJaaaaaJaa«a{aaaaaja.—a
P : С: T: У: Ф
.....................>....
Ci Ti У: Ф: X
вааа^аав a a^a a a•^aaiaajea a a
Ti yi Фi xi ц
3 i и
ni й
-••c....
Й! К
aaaa{aaaaa
Ki Л
7: M
M: H
ui Mi IIj О
oi n
riiP.
pic
ci f
Й= К
Ki Л
м= н
,Л: КС Hi Oi П
Mi iii oi rii p
—-i....>—«...>•—
Hi Oi П: P : C
a a.. { a aaa aj a a a a {a a a^w J a a a a
o' ni p i ci т
П - H Cj T - У
pi cIt; yi Ф
Cjj: У j Ф[ X
У: Ф‘: Xi Il i Ч
ааа * •• аЧ••••?aе..1a aaai
У: ф
ф: X
Д1.Ч
Ч: Ш
4i iijiii ь[ ыТ si ю
Приложение 2 1
Число простых чисел
х>70
< л(х) < .
logx-1/2---------Iogx-3/2
Размер Вселенной -
1027 м = 1042 радиусов ядра атома водорода.
Приложение 2.2
Псевдопростые числа
Число и - псевдопростое, если оно составное и делит 2"'* - 1. Множе-
ство псевдопростых чисел бесконечно. Псевдопростые до 2000: 341, 561, 645,
1105, 1387, 1729,1905. Число и псевдопростое по основанию а, если (а, и) = 1
и п делит ап 1 - 1. Число и называют числом Кармихаэля (Carmichael
R.D.) или абсолютно псевдопростым, если оно псевдопростос для всех
чисел, взаимно простых с ним. Множество чисел Кармихаэля бесконечно
(1994 г.). Число 341 псевдопростое, но нс абсолютно псевдопростое. Из-
вестны таблицы всех псевдопростых чисел < 25 109.
Доказать, что:
а) Число 341 не абсолютно псевдопростое (не псевдопростос по осно-
ванию 11),
б) Если числа 6m+l, 12m+l, 18т+1 все простые, то число
n = (6m + 1) • (12m + 1) • (18m + 1) абсолютно псевдопростое.
92
Приложение 4.1
Число неприводимых и примитивных
много членов
п р = 2 р = 3 р = 5 р = 7
а2(и) Ьз(п) ««(«) Ы«) в7(л) Л7(л)
1 2 1 3 1 5 2 7 2
2 1 1 3 2 10 4 21 8
3 2 2 8 4 40 20 112 36
4 3 2 18 8 150 48 588 160
5 6 6 48 22 624 304
6 9 6 Ш 48
7 18 18 312 156
8 30 16
9 56 48
10 99 60
И 186 176
Приложение 4.2
Неприводимые многочлены
над полем
f(x) = a(, + atx + атХ1 +...+ a„x" = (а0, at,а„~), и = deg/, е - ord/
n = 1; «1 e n = 5; a0 ax a2 a3 a4 as r
1 1 I 100101 31
и = 2; a0 «1 a2 101001 31
1 1 1 3 101111 31
n = 3; aQaxa2a3 111011 31
10 11 7 110111 31
110 1 7 111101 31
n = 4; аоЛ1а2д3а4 n = 6; aQaxa2a3a4a$a6
10011 15 1000011 63
1100 1 15 1 10000 1 63
11111 5 1100111 63
1110011 63
1011011 63
1 101101 63
1010111 21
1110101 21
1001001 9
94
Приложение 4.3
Примитивные многочлены над полем
степени п с наименьшим
числом ненулевых членов
Символом к I m обозначается многочлен f = 1+ х* + х1 + х"1
п f П f Л f
1 1 36 11 36 70 13 570
2 1 2 37 1 2 3 4 5 37 71 1 23 71
3 13 38 1 56 38 72 1 2 3 4 6 72
4 1 4 39 4 39 73 2 3 473
5 25 40 3 4 540 74 3 47 74
6 16 41 3 41 75 13 675
7 1 7 42 1 2 3 4 5 42 76 2 4576
8 2348 43 3 46 43 77 2 5 677
9 49 44 2 5644 78 1 2 778
10 3 10 45 1 3 445 79 2 3 479
11 2 11 46 1 2 3 5 8 46 80 1 235780
12 1 48 12 47 5 47 81 4 81
13 134 13 48 1 245748 82 1 4 6 7 8 82
14 135 14 49 4 56 49 83 24783
15 1 15 50 23450 84 1 3 5 7 8 84
16 23 516 51 13 651 85 12 885
17 3 17 52 3 52 86 2 5 686
18 7 18 53 12653 87 1 5787
19 12519 54 2345654 88 1 3 4 5 8 88
20 3 20 55 12 655 89 35689
21 2 21 56 2 47 56 90 2 3 590
22 122 57 2 3 557 91 23 56 7 91
23 5 23 58 1 5 658 92 2 5 692
24 1 27 24 59 1 3 4 5 6 59 93 2 93
25 3 25 60 160 94 15 694
26 1 2626 61 1 2 561 95 1 2 4 5 6 95
27 1 2 527 62 3 5662 96 2 3 4 6 7 96
28 3 28 63 163 97 6 97
29 2 29 64 1 3 464 98 1 2 3 4 7 98
30 14630 65 13 465 99 45799
31 3 31 66 2 3 5 6 8 66 100 2 7 8 100
32 1 2 22 32 67 12567
33 13 33 68 1 57 68 107 123 57107
34 1 2 27 34 69 2 5669 127 1 127
95
Приложение 4.4
Примитивные многочлены
над полями и Г7
f(x) = a„ • х" +... + О1Х + a0 = (a„,... ab a0)
n p = 3 f n p = s f n p-7 f n p-7 f
1 11 1 12 1 12 3 1334
2 112 13 14 1352
122 2 112 2 113 1354
3 1021 123 123 1362
1201 133 125 1422
1121 142 135 1432
1211 3 1032 145 1434
4 10012 1033 153 1444
10022 1042 155 1504
11002 1043 163 1524
11122 1102 3 1032 1532
11222 1113 1052 1534
12002 1143 1062 1542
12112 1203 1112 1564
12212 1213 1124 1604
1222 1152 1612
1223 1154 1632
1312 1214 1644
1322 1242 1654
1323 1262 1662
1343 1264 1664
1403 1304
1412 1314
1412 1322
96
Приложение 4.5
Таблицы индексов для полей
\ из 4, 8, 16 и 32 элементов
ind ind Fie ind Fn bid F31
0 01 5 1011 8 11010 27 10110
1 10 6 1111 9 11101 28 00101
2 11 7 0111 10 10011 29 01010
9 0101 11 01111 30 10100
ind Fs 10 1010 12 11110
6 001 11 1101 13 10101
1 010 12 ООП 14 00011
2 100 13 0110 15 00110
3 101 14 1100 16 01100
4 111 17 11000
5 Oil bid lit 18 11001
6 110 0 00001 19 11011
1 00010 20 11111
bid Fu 2 00100 21 10111
0 0001 3 01000 22 00111
1 0010 4 10000 23 OHIO
2 0100 5 01001 24 11100
3 1000 6 10010 25 10001
4 1001 7 01101 26 01011
Приложение 5.1
Простые числа Мерсенна (1995 г.)
Простые числа вида 2я- 1, где р - простое число:
2 3 5 7 13 17
19 31 61 89 107 127
521 607 1279 2203 2281 3217
4253 4423 9689 9941 11213 19937
21701 23209 44497 86243 110503 132049
216091
97
Приложение S,
Разложение на простые множители
чисел Мерсенна
M(n) = 2"- 1
И М(н) п М(п)
2 3
3 7 37 223616318177
5 31 39 7 79 8191 121369
7 127 41 13367 164511 353
9 7-31 43 431-9719-2099863
11 2389 45 7-31-73-151-631-23311
13 8191 47 2351 4513 13264529
15 731 151 49 127-4432676798593
17 131071 51 7 103 2143 11119 131071
19 524287 53 6361-69431-20394401
21 7-7-127-337 55 23-31-89-881-3191-201961
23 47 178481 57 7-32377-524287-1212847
25 31 601 1801 59 179951-3203431780337
27 7-73-262657 61 2305843009213693951
29 233-1103-2089 63 7-7-73-127-337-92737-649657
31 2147483647 65 31 8191-1462951435581111
33 7-23-89-599479 67 193707721-761838257287
35 31-71 127-122921 69 7-47-178481-10052678938039
98
Продолжение пр ил о ж. 5.2
п М(п)
71 228479 48544121 212885833
73 \ 439 2298041 9361973132609
75 \ 7 31 151 601 1801 100801 10567201
77 23 89 127 581283643249112959
79 2687 202029703 1113491139767
81 7 73 2593 71229 262657-97685839
83 167 57912614113275649087721
85 31 131071 9520972806333758431
87 7 233 1103-2089 4177 9857737155463
89 618970019642690137449562111
91 127 911 8191 112901153 23140471537
93 7-2147483647 858812288653553079
95 31 191-524287 429778751 30327152671
97 11447 13842607235828485645766393
99 7-23 73 89-199 153649 59947933057806959
101 74323392098719 341117531003194129
103 2550183799-3976656429941438590393
105 7 7 31 71-127 151 337 29191-106681 122291 152041
107 162259276829213363391578010288127
109 745988807 870035986098720987332873
111 7-223-321679-26295457 319020217 616318177
113 3391 23279 65993 1868569 1066818132868207
115 31 47 14959 178481 4036961-36365077109884041
117 7 79 937 6553-8191-86113 121369 7830118297
119 127 239 20231 131071 62983048367 131105292137
121 23 89-727 1786393878363164227858270210279
123 7-13367-3887047 164511353 1 ^7722253954175633
125 31 601 1801 269089806001 4710883168879506001
127 170141183460469231731687303715884105727
129 7-431 9719-2099863-11053036065048294753459639
131 263 10350794431055162386718619237468234569
99
Продолжение п р и л о ж. 5.2
п М(п) / |
133 127 524287 163537220852725398851434325720959
135 7 31 73-151-271 631 23311-262657 348031 49971617830801
137 32032215596496435569 5439042183600204290159
139 5625767248687 123876132205208335762278423601
141 7 2351 4513 13264529 4375578271 6466750352532578729
143 23 89 8191 724153 158822951431 57682172113400990737
145 31 233 1103 2089 26798951577838628146090027494144991
147 7-7-7-127-337 4432676798593-2741672362528725535068727
149 8665626856628298Л51 8235109336690846733986161
БИБЛИОГРАФИЧЕСКАЯ СПРАВКА
Август (63 г. до н. э. - 14 г. н. э.), римский император (43 г. до н. э. - 14 г. н. э.).
Аристотель (384-322 гг. до н. э), древнегреческий философ.
Бестужев-Рюмин Алексей Петрович (1693-1766), в 1740-1741 гг. кабинет-
министр, в 1744-1766 гг. канцлер.
Буркхард Людвиг (1784-1817), швейцарский ученый и путешественник, член
Британского Королевского африканского общества.
Валлис Джои (1616-1703), английский математик.
Виженер (1523-1596), французский посол в Риме, написал большой труд о
шифрах, создал свою систему шифра. Квадратный шифр Инженера
на протяжении почти 400 лет не был дешифрован, считался нсде-
шифруемым шифром; использовался как военный шифр.
Владимир Всеволодович (1193-1229), внук Юрия Долгорукого.
Галуа Эварист (1811-1832), французский математик, заложил основы со-
временной алгебры, построил теорию конечных полей.
Гашек Ярослав (1883-1923), чешский писатель-сатирик, автор романа
"Похождения бравого солдата Швейка во время мировой войны"
(1921-1923).
Гельфонд Александр Осипович (1906-1968), советский математик, основные
труды которого принадлежат теории чисел и теории функций ком-
плексного переменного, решил полностью 7-ю проблему Гильберта.
Геродот (484-424 гг. до н. э.), древнегреческий историк.
Гольдбах Христиан (1690-1764), математик, член Петербургской АН с 1725 г.
Грозный Бедржих (1879-1952), чешский ассириолог, первый расшифровал
хеттскую клинопись.
101
Гротенфенд Георг Фридрих (1775-1853), немецкий филолог, специалист п<
дрсвнеиталианским языкам, достиг больших успехов в дешифровке
древнеперсидских клинописных текстов.
Даниил Заточник (XII в ), уроженец Юж. Переславля, с его именем связы-
вают "Слово Даниила Заточника".
Декарт Рене (1596-1690), французский философ и математик.
Диофант (середина III в. н.э.) - считается основателем теории неопрсдслен
ных уравнений.
Дойл Артур Конан (1859-1930), английский писатель, один из классиков
детективного жанра в литературе.
Евклид (ок. 340 г. - ок. 287 г. до н.э.), древнегреческий математик, автор
первого дошедшего до нас трактата по математике.
Елизавета Петровна (1709-1761), дочь Петра I, императрица с 1741 г.
Карацуба Анатолий Алексеевич (род 31.01 37 г.), крупный специалист
по теории чисел.
Кардано Джероламо (1501-1576), итальянский математик, философ и врач.
Кирхер Афанасий (1601-1680), немецкий богослов и естествоиспытатель,
автор работ по физике, математике и лингвистике.
Лагранж (1736-1813), французский математик, механик и астроном.
Ламе Габриель (1792-1870). французский математик, с 1820 по 1832 г. вел
преподавание в Петербурге в Институте инженеров путей сообщения.
Получил доказательство теоремы Ферма для п = 7, предложил
ошибочное доказательство теоремы Ферма, основанное на предпо-
ложении, что для чисел вида Ло+ + ... + Ьп где Ло, ..., ЬпЛ -
целые числа, а £ - примитивный корень степени п из 1, имеет место
однозначность разложения на множители.
Лепсис Рихард (1810-1884). немецкий египтолог.
Мерсенн Марен (1588-1648), французский физик, математик и философ;
основные труды по геометрии; вел обширную переписку с огромным
крутом ученых Франции и других стран, выполняя роль центра евро-
пейской научной взаимной информации.
Мёбиус (1790-1868), немецкий математик.
102
Морзе Сэмюэль Финли Бриз (1791-1872), американский художник и изобре-
татель телеграфного аппарата.
Нибур Карстен (1733-1815), датский путешественник и исследователь.
Hemp I (1672-1725), русский царь с 1689 г, российский император с 1721 г.
Плутарх (45-127 гг. н. э.), древнегреческий историк.
По Эдгар Аллан (1859-1930), американский писатель, родоначальник детек-
тивной литературы ("Убийство на улице Морг", "Золотой жук").
Полибии (200-120 гг. до и. э ), древнегреческий историк.
Рузвельт Франклин Делано (1882-1945), 32-й президент США с 1933 г.
Светоний Гай Транквил (707-140?), римский историк.
Страбон (64/63 гг. до н.э. - 23/24 гг. н.э), греческий географ.
Толстой Петр Андреевич (1645-1729), русский дипломат, посол в Осман-
ской империи; с 1718 г. начальник Тайной канцелярии.
Тритемиус (1462-1516), аббат, религиозный деятель
Ферма Пьер (1601—1665), французский математик; анализ, аналитическая
геометрия, теория вероятностей, оптика - вот области математики
и физики, в развитии которых весьма заметен вклад Ферма. Но
главная привязанность Ферма - теория чисел.
Цезарь Гай Юлий (100—44 гг. до н.э), полководец, римский император в
46-44 гг. до н. э.
Шампольон Жан Франсуа (1790-1833), французский египтолог, разработал
основные принципы дешифровки древнеегипетского иероглифиче-
ского письма.
Эйлер Леонард (1707-1783), математик, механик и физик, член Петербург-
ской АН.
Юнг Томас (1773-1829), автор ряда трудов по физике, расшифровке египет-
ских иероглифов.
103
ЛИТЕРАТУРА
1. Айерлэнд К., Роузен М. Классическое введение в современную теорию
чисел. -М.: Мир, 1987.
2. Аршинов М.Н., Садовский Л.Е. Коды и математика. - М.: Наука. 1983.
3. Берлекэмп Э. Алгебраическая теория кодирования - М. Мир, 1971.
4 Биркгоф Г., Барти Т. Современная прикладная алгебра. - М.: Мир, 1976.
5. Болл У., Коксетер Г. Математические эссе и развлечения. - М : Мир,
1986.
6. Ван дер-Варден Б.Л. Алгебра. - М. : Наука, 1976.
7. Виленкин Н.Я. Математика и шифры И Квант. 1977. № 8.
8. Виноградов И.М. Основы теории чисел. - М.. Наука, 1982.
9. Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в тео-
рию чисел. -М : МГУ, 1984.
10. Гарднер М. От мозаик Пенроуза к надежным шифрам - М.: Мир, 1993.
11. Гашков С.Б., Чубариков В.Н. Арифметика. Алгоритмы Сложность вы-
числений. - М.: Наука, 1996.
12. Геродот. История. - М : Научно-издат. центр "Ладомир", 1993.
13. Гилл А. Линейные последовательные машины. - М.. Мир, 1974.
14. Диффи У., Хелмэн М. Защищенность и имитостойкость. Введение в
криптографию //ТИИЭР. 1979. Т. 67. № 3. С. 71-109.
15. Добльхофер Э. Знаки и чудеса.*- М.: Изд-во восточной литературы, 1963.
16. Дориченко С.А., Ященко В.В. 25 этюдов о шифрах. - М.. ТЕИС, 1994
17. Зарисский О., Самюэль П. Коммутативная алгебра. - М.: Изд-во ино-
странной литературы, 1963. Т. 1
18. История древнего мира. Кн. 1 Ранняя древность. - М.: Наука, 1983.
19. Карацуба А.А., Гофман ЮЛ. Умножение многозначных чисел на авто-
матах // ДАН СССР. 1962. Т 145. № 2. С. 293-294.
20. Карацуба А.А. Сложность вычислений//Тр. МИАН. 1995. Т 211.
С. 186-202.
104
21 Керам К. Боги, гробницы, ученые. - М.: Наука, 1986.
.'2 КнутД. Искусство программирования для ЭВМ. - М.: Мир, 1977. Т. 2.
23. Коробов Н.М. Распределение невычетов и первообразных корней в ре-
куррентных рядах // ДАН СССР. 1953. Т. 88. № 4. С. 603-606.
24. Кострикин А.И. Введение в алгебру. М.: Наука, 1994.
.’ 5. Коэн X., Ленстра X. Проверка чисел на простоту и суммы Якоби // Ки-
бернетический сборник. 1987. Выл. 24. С 99-146.
26. Лебедев А.Н. Криптография с открытым ключом и возможности ее прак-
тического применения И Защита информации. 1992 Выл. 2 С. 129-147.
27. Лидл Р, Нидеррайтер Г. Конечные поля. В 2-х т. - М.: Мир, 1988.
28. Манин Ю.И., Панчишкин А.А. Введение в теорию чисел. - М.: ВИНИТИ,
1990.
29. Миллер Г.Л. Гипотеза Римана и способы проверки простоты чисел//
Кибернетический сборник. 1986. Вып. 23. С. 31-50.
30. Нечаев В.И. К вопросу о сложности детерминированного алгоритма для
дискретного логарифма// Математические заметки. 1994. Т. 55. Вып. 2.
С. 91-101.
31 Нечаев В. И. Распределение на части периода линейной рекуррентной после-
довательности над конечным полем Тезисы Ш Международной конкурен-
ции "Современные проблемы теории чисел и ее приложения". Тула, 1996.
С. 107.
32. Нечаев В.И. Распределение знаков в последовательности прямоуголь-
ных матриц над конечным полем // Тр. МИАН. 1996. Т. 218. С. 335-342.
33. Нечаев ВИ. Сложность дискретного логарифма И Научные труды МПГУ.
1994. С. 46-49.
34. Нечаев В.И. Тригонометрические суммы для рекуррентных последова-
тельностей // ДАН СССР. 1972. Т. 206. № 4. С. 811-814.
35. Плутарх. Избранные жизнеописания В2-хт -М.: Правда, 1987
36. Рибенбойм П. Рекорды простых чисел И УМН. 1987. Т. 42. Вып. 2(257)
С. 119-176.
37. СаломааА. Криптография с открытым ключом. - М.: Мир, 1996.
38. Светонии Г. Т. Жизнь двенадцати цезарей. - М.: Правда, 1991.
39. Соболева Т.А. Тайнопись в истории России. - М., 1994.
40. Страбон. География. - М.: Научно-издат. центр "Ладомир", 1994.
105
41 Уильямс X. Проверка чисел на простоту’ с помощью вычислительных
машин// Кибернетический сборник. 1986. Вып. 23. С. 51-99.
42. Фейман Р., Лейтон Р., Сендс М. Фейнмановские лекции по физике. -
М.: Мир. 1965.
43. Юшкевич А.П., Копелевич Ю.Х. Христиан Гольдбах. - М.: Наука, 1983.
44. Alanen J.D., Knuth Е. Tables of finite Fields, Sanknya, the Indian journal
of statistics, ser. A 1964. V. 26. Part 4. P 305-328.
45. Blake J.F., Fuji-Hara R., Mullin R.S., Vanstone S.A. Computing loga-
rithms in finite fields of characteristic two. IEEE. Trans. Information Theoiy.
1984. V. 30. P. 587-594
46. Buchman J., Paulus S. Algorithms for finite abelian groups. Number Theo-
retic and Algebraic Methods in Computer Science. Conference Abstracts.
1993. P. 22-27.
47. Coppersmith D. Fast evolution of logarithms in fields of two. IEEE. Trans.
Information Theory. 1984. V. 30. P. 587-594.
48. Mitrinovic D.S., Popadic M.S. Inequalities m Number Theoiy . University of
Niche, 1978
49 Pohlig S.C., Hellman M.E. An improved algorithm for computing loga-
rithms over GF(p) and its Cryptographic significance. IEEE. Trans. Infor-
mation Theoiy. 1978. V. 24. P 106-110.
50 Schroder M.R. Number Theory in Science and Communication. Springer,
1986.
51. Shanks D. Class number A theory of factorization and genera. Proc. Symp.
Pure Math. V. 20. AMS, 1970. P 415-440.
52. Sierpinski W. Elementary Theoiy'of Numbers. Warzawa, 1964.
ОГЛАВЛЕНИЕ
Предисловие. Элементы криптографии................................... 7
Обозначения ......................................................... 8
Глава 1. Из истории криптографии................................. 9
§1 . Криптография ........................................... 9
§2 . Тайнопись в России..................................... 16
§3 . Из истории второй мировой войны ..................... 20
§4 . Криптография и археология.............................. 20
Ответы к шифрованным сообщениям ........................ 22
Глава 2. Цифровое шифрование ................................... 23
§1 . Сравнение арифметических операций по их трудоемкости ..... 23
§2 . Криптосистема без передачи ключей ..................... 27
§3 . Криптосистема с открытым ключом........................ 28
§4 . Электронная подпись ....................................................................... 31
Глава 3. Конечные поля.......................................... 34
§1 . Характеристика поля 35
§2 . Существование конечного поля........................... 37
§3 . Мультипликативная группа конечного поля................ 38
Глава 4. Неприводимые и примитивные
над конечным полем многочлены ........................ 42
§1 . Неприводимые многочлены................................ 42
§2 . Порядок многочлена над конечным полем ....................................... 45
§3 . Конструкция конечного поля из р" элементов............. 41
Ответы и указания к решению вопросов.................... 48
Глава 5. Последовательности над конечным полем...................... 49
§1 . Псевдослучайные последовательности и их применение
в криптографии .............................................. 49
§2 . Алгебра последовательностей над конечным полем ........ 51
107
§3 . Линейные рекуррентные последовательности
над конечным полем . ..............................................
§4 . Аннулирующие многочлены.......................................
§5 . Регистр сдвига............................... ............................
Глава 6. Дискретный логарифм ..............................................
§1 . Экспоненциальный открытый ключ ............................................ь...
§2 . Вычисление дискретного логарифма ................................................
§3 . Историческая справка..........................................
Ответы и указания к решению вопросов..........................
Глава 7. Линейные рекуррентные
последовательности как псевдослучайные
последовательности........................................................
§1 . Число появлений наборов фиксированных знаков на полном периоде
максимальной линейной рекуррентной последовательности .............
§2 . Свойства решений линейного рекуррентного уравнения ...........
§3 . Суммы с характерами ..........................................
§4 Максимальные линейные рекуррентные последовательности
как псевдослучайные последовательности ... ........................
Алгебраическое дополнение L
Конечные группы. Теорема Лагранжа .........................................
Алгебраическое дополнение И.
Простое расширение поля. Поле разложения многочлена .......................
Алгебраическое дополнение III.
Конечное расширение...........
Арифметическое дополнение I
Принцип обращения Мёбиуса .................................................
Арифметическое дополнение II.
Характеры конечной группы..................................................
Приложения................................
Приложение 1.1.
Приложение 1.2.
Приложение 1.3.
Приложение 1.4.
Морзе азбука (русский вариант)..................
Русский алфавит.................................
Цифирь Петра I для ILA. Толстого................
Таблица относительных частот встречаемости
букв в русском тексте ..........................
108
Приложение 1.5. Расположение букв русского алфавита
по их относительной частоте ............................... 90
Приложение 1.6. Греческий алфавит ......................... 90
Приложение 1.7. Таблица Виженера ......................... 91
Приложение 2.1. Число простых чисел........................ 92
Приложение 2.2. Псевдопростые числа ....................... 92
Приложение 4.1. Число неприводимых и примитивных
многочленов ............................... 93
Приложение 4.2. Неприводимые многочлены над полем Ft....... 94
Приложение 4.3. Примитивные многочлены над полем Ft
степени п с наименьшим числом
ненулевых членов .......................... 95
Приложение 4.4. Примитивные многочлены над полями
Fs,FshF7................................................... 96
Приложение 4.5. Таблицы индексов для полей из 4,8, 16 и
32 элементов.............................................. 97
Приложение 5.1. Простые числа Мерсенна ................... 97
Приложение 5.2. Разложение на множители чисел Мерсенна..... 98
Библиографическая справка.................................. 101
Литература ................................................ 104