Введение в теорию чисел. Алгоритм RSA

Коутинхо С.

Криптография! Многие еще с детства заинтригованы этим процессом. Кто не помнит «пляшущих человечков» Конан Дойля? Но реальная схема шифрования и проще, и сложнее, чем об этом написано в знаменитом рассказе классика.

Увидев в названии математическую теорию, некоторые из вас сочтут книгу скучной и неинтересной. Ошибаетесь! Пособие написано живо, интересно и очень доступно. Для понимания сути достаточно знаний средней школы. Но, несмотря на простой стиль изложения, все утверждения снабжены строгими доказательствами или ссылками на литературу.

Круг читателей очень широк: от школьников, интересующихся теорией чисел или шифрованием, до банковских и корпоративных программистов, желающих глубже вникнуть в основы своей деятельности.

Москва, изд. «Постмаркет», 2001 г.

ISBN 5-901095-09-Х

Количество страниц: 328.

Содержание книги «Введение в теорию чисел. Алгоритм RSA»:

7 Предисловие
10 Предисловие автора
14 Глава 1. Введение
- 14 § 1.1. Криптография
- 18 § 1.2. Система шифрования RSA
- 21 § 1.3. Системы символьных вычислений
- 25 § 1.4. Греки и целые числа
- 27 § 1.5. Ферма, Эйлер и Гаусс
- 30 § 1.6. Проблемы теории чисел
- 33 § 1.7. Теоремы и доказательства
39 Глава 2. Фундаментальные алгоритмы
- 39 § 2.1. Алгоритмы
- 43 § 2.2. Алгоритм деления
- 45 § 2.3. Теорема деления
- 47 § 2.4. Алгоритм Эвклида
- 51 § 2.5. Доказательство корректности алгоритма Эвклида
- 54 § 2.6. Расширенный алгоритм Эвклида
- 58 Упражнения
62 Глава 3. Разложение на множители
- 62 § 3.1. Теорема о разложении
- 64 § 3.2. Существование разложения
- 68 § 3.3. Эффективность алгоритма деления методом проб
- 69 § 3.4. Алгоритм Ферма разложения на множители
- 71 § 3.5. Доказательство корректности алгоритма Ферма
- 74 § 3.6. Одно фундаментальное свойство простых чисел
- 76 § 3.7. Греки и иррациональности
- 79 § 3.8. Единственность разложения
- 83 Упражнения
88 Глава 4. Простые числа
- 88 § 4.1. Полиномиальная формула
- 92 § 4.2. Экспоненциальные формулы: числа Мерсенна
- 95 § 4.3. Экспоненциальные формулы: числа Ферма
- 96 § 4.4. Праймориальная формула
- 98 § 4.5. Бесконечность множества простых чисел
- 105 § 4.6. Решето Эратосфена
- 110 Упражнения
115 Глава 5. Арифметика остатков
- 116 § 5.1. Отношение эквивалентности
- 121 § 5.2. Сравнения
- 125 § 5.3. Арифметика остатков
- 129 § 5.4. Критерий делимости
- 132 § 5.5. Степени
- 133 § 5.6. Диофантовы уравнения
- 135 § 5.7. Деление по модулю n
- 139 Упражнения
143 Глава 6. Индукция и Ферма
- 143 § 6.1. Ханой! Ханой!
- 150 § 6.2. Математическая индукция
- 155 § 6.3. Теорема Ферма
- 159 § 6.4. Вычисление корней
- 165 Упражнения
171 Глава 7. Псевдопростые числа
- 171 § 7.1. Псевдопростые числа
- 175 § 7.2. Числа Кармайкла
- 180 § 7.3. Тест Миллера
- 185 § 7.4. Тестирование простоты и системы символьных вычислений
- 188 Упражнения
192 Глава 8. Системы сравнений
- 192 § 8.1. Линейные уравнения
- 194 § 8.2. Астрономический пример
- 197 § 8.3. Китайский алгоритм остатков: взаимно простые модули
- 202 § 8.4. Китайский алгоритм остатков: общий случай
- 204 § 8.5. Снова степени
- 206 § 8.6. Посвящение в тайну
- 210 Упражнения
213 Глава 9. Группы
- 213 § 9.1. Определения и примеры
- 216 § 9.2. Симметрии
- 222 § 9.3. Интерлюдия
- 227 § 9.4. Арифметические группы
- 232 § 9.5. Подгруппы
- 234 § 9.6. Циклические подгруппы
- 237 § 9.7. В поисках подгрупп
- 239 § 9.8. Теорема Лагранжа
- 242 Упражнения
247 Глава 10. Мерсенн и Ферма
- 247 § 10.1. Числа Мерсенна
- 251 § 10.2. Числа Ферма
- 254 § 10.3. И снова Ферма
- 256 § 10.4. Тест Люка - Лемера
- 261 Упражнения
264 Глава 11. Тесты на простоту и примитивные корни
- 264 § 11.1. Тест Люка
- 269 § 11.2. Еще один тест на простоту
- 272 § 11.3. Числа Кармайкла
- 273 § 11.4. Предварительные замечания
- 276 § 11.5. Примитивные корни
- 278 § 11.6. Вычисление порядков
- 280 Упражнения
284 Глава 12. Система шифрования RSA
- 284 § 12.1. О начале и конце
- 286 § 12.2. Шифровка и дешифровка
- 289 § 12.3. Почему она работает?
- 292 § 12.4. Почему система надежна?
- 293 § 12.5. Выбор простых
- 297 § 12.6. Проблема подписи
- 299 Упражнения
303 Кода
309 Приложение. Корни и степени
- 309 § П.1. Квадратные корни
- 312 § П.2. Алгоритм степеней
314 Литература
319 Дополнительная литература
321 Предметный указатель