Читать онлайн «Введение в теорию чисел. Алгоритм РСА (первые 212 страниц)»

С. Коутинхо ВВЕДЕНИЕ В ТЕОРИЮ ЧИСЕЛ АЛГОРИТМ RSA Перевод с английского С. А. Кулешова Под редакцией С. К. Ландо ПОСТМАРКЕТ МОСКВА 2001 Криптография! Многие еще с детства заинтригованы этим процессом. Кто не помнит «пляшущих человечков»Конан Дой- Дойля? Но реальная схема шифрования и проще, и сложнее, чем об этом написано в знаменитом рассказе классика. С одной системой шифрования и знакомит эта книга. Увидев в названии математическую теорию, некоторые из вас сочтут книгу скучной и неинтересной. Ошибаетесь! Посо- Пособие написано живо, интересно и очень доступно. Для понима- понимания сути достаточно знаний средней школы. Но несмотря на простой стиль изложения, все утверждения снабжены строги- строгими доказательствами или ссылками на литературу. Круг читателей очень широк: от школьников, интересую- интересующихся теорией чисел или шифрованием, до банковских и кор- корпоративных программистов, желающих глубже вникнуть в ос- основы своей деятельности. Содержание Предисловие 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.