Коутинхо С. Введение в теорию чисел. Алгоритм RSA ОНЛАЙН

Коутинхо С. Введение в теорию чисел. Алгоритм 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

Поделиться ссылкой:
  • Добавить ВКонтакте заметку об этой странице
  • Мой Мир
  • Facebook
  • Twitter
  • LiveJournal
  • В закладки Google
  • Яндекс.Закладки
  • Сто закладок
  • Blogger
  • Блог Li.ру
  • Блог Я.ру
  • Одноклассники
  • RSS

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Наш сайт находят по фразам:

×