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

Для понимания сути достаточно знаний средней школы. Но несмотря на простой стиль изложения, все утверждения снабжены строгими доказательствами или ссылками на литературу.
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



Читать онлайн
скачать бесплатно


Теги:
Теория чисел, Коутинхо теория чисел

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