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