Курс теории чисел и криптографии - Коблиц Н.
Курс теории чисел и криптографии
Автор: Коблиц Н.Издательство: Москва: Научное изд-во ТВП
Год издания: 2001
Страницы: 254
Читать: 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125
Скачать:
Н. Коблиц
КУРС ТЕОРИИ ЧИСЕЛ И КРИПТОГРАФИИ
Москва: Научное изд-во ТВП, 2001, х+254 с.
Цель данной книги — ввести читателя в те области арифметики, как классические, так и самые современные, которые находятся в центре внимания приложений теории чисел, особенно криптографии. Предполагается, что знание высшей алгебры и теории чисел ограничено самым скромным знакомством с их основами; по этой причине излагаются также необходимые сведения из этих областей математики. Авторами избран алгоритмический подход, причем особое внимание уделяется оценкам эффективности методов, предлагаемых теорией. Особенностью книги является изложение совсем недавно разработанных приложений теории эллиптических кривых. Перевод на русский язык осуществлен с оригинала второго издания, существенно пересмотренного по сравнению с первым изданием и снабженного обновленным списком литературы. Каждая глава включает в себя тщательно составленную подборку задач, как правило, снабженных подробными указаниями и решениями.
Все это позволяет рекомендовать книгу не только в качестве ценного пособия для общетеоретической подготовки специалистов по защите информации, но и как полезный источник примеров практической применимости целого ряда абстрактных разделов математики и кибернетики. Книга прекрасно подходит и
для самообразования.
СОДЕРЖАНИЕ
Предисловие V
Предисловие ко второму изданию vii Глава I. Некоторые вопросы элементарной теории чисел 1
§ 1. Временные оценки сложности арифметических операций 1
§ 2. Делимость и алгоритм Евклида 13
§ 3. Сравнения 20
§ 4. Некоторые применения к разложению на множители 30
Глава II. Конечные поля и квадратичные вычеты 34
§ 1. Конечные ПОЛЯ 36
§ 2. Квадратичные вычеты и закон взаимности 47
Глава III. Криптография 61
§ 1. Некоторые простые криптосистемы 61
§ 2. Шифрующие матрицы 73
Глава IV. Открытый ключ 91
§ 1. Суть криптографии с открытым ключом 91
§ 2. Криптосистема RSA 101
§ 3. Дискретное логарифмирование 107
§ 4. Задача о рюкзаке 123
§ 5. Протоколы с нулевым разглашением и скрытая передача 130
Глава V. Простота и факторизация 139
§ 1. Псевдопростые числа 140
§ 2. Ро-метод 155
§ 3. Факторизация Ферма и факторные базы
§ 4. Метод цепных дробей
§ 5. Метод квадратичного решета
Глава VI. Эллиптические кривые
§ 1. Основные факты
§ 2. Криптосистемы на эллиптических кривых
§ 3. Критерий простоты, использующий эллиптические кривые
§ 4. Разложение на множители при помощи эллиптических кривых
Ответы к упражнениям
Предметный указатель
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
160 174 180 188
188 200 212 217 227 255
Абелева группа 37 -, тип 197
автоморфизм 35, 41 Адлемана-Померанца-Румели тест на
простоту 151 Адлемана-Хуана тест на простоту
215-216 алгебраический элемент 35 алгоритм 10
- Берлекампа 116
- вероятностный 95, 104-105, 141-142
- детерминистический 142
- дискретного логарифмирования
113-118
- индексный 114-118
- Силвера-Полига-Хеллмана 113-
114,208
- факторных баз 115-116, 166
- Шуфа 202, 207 алфавит 92
аутентичность, подлинность 97, 105 аффинная плоскость 192 аффинное отображение 64, 67, 76, 84 Бесконечно удаленная прямая 192 бесконечность 193
- - точка 189, 193 биграмма 61 бит 3 «больших и малых шагов» метод 114 Бонд Джеймс 90, 210, 236, 239 бросание монетки 100, 106, 240 быстрорастущий набор 123 Я-число 162, 180-181
Вейля
- гипотеза 198
- спаривание 204 векторное пространство 34 вероятностное шифрование 99 вероятностный алгоритм 95, 104-105,
141-142 вещественные точки на
эллиптической кривой 199, 251 взаимно простые (числа) 16 Виженера шифр 74 Вильсона теорема 28 возведение в степень 25-26, 107
- в кольце 26, 107 временные оценки 5 для
- алгоритма Евклида 15-16, 18, 19
- алгоритма факторных баз 166-172
- арифметических операций 3-8
- возведения в степень в кольце
вычетов 26
- извлечения квадратного корня по
модулю р 57-58
- метода квадратичного решета 185
- нахождения обратного 21
- перевода в новую систему
счисления 10-11
- ро-метода 158-159
- теста Миллера-Рабина на простоту
153
- точек на эллиптической кривой 201
- факторизации на эллиптической
кривой 224-226
- факторизационных алгоритмов 171-
172
вскрытие кода 63 вычет
- квадратичный 49
- наименьший абсолютный 162
- по модулю m 20-21, 219 Галуа расширение поля 35 гауссова сумма 50, 52, 151 гауссовы числа 19, 42, 48, 193 гладкая точка 189
гладкое целое 113
глобальная эллиптическая кривая 208
граф 130
группа
- абелева 37
- циклическая 38 Двоичная
- операция 3
- система счисления 1-3 двоичный разряд (бит) 3 делимость 13
- точная 13 делитель 13
- нетривиальный 13
- собственный 13 делящая точка 195 детерминистический алгоритм 142 дешифрование 61
-, ключ 91
-, преобразование 61 дзета-функция 198
- на эллиптической кривой 198 дискретный логарифм 107-108
- на эллиптической кривой 203 DES (стандарт шифрования данных)
