Читать онлайн «Введение в теорию чисел. Алгоритм RSA»

С. Коутинхо ВВЕДЕНИЕ В ТЕОРИЮ ЧИСЕЛ АЛГОРИТМ RSA Перевод с английского С. А. Кулешова под редакцией С. К. Ландо ПОСТМАРКЕТ МОСКВА 2001 С. Коутинхо. Введение в теорию чисел. Алгоритм RSA. Москва: Постмаркет, 2001. - 328 с. Криптография! Многие еще с детства заинтригованы этим процессом. Кто не помнит «пляшущих человечков» Конан Дойля? Но реальная схема шифрования и проще, и сложнее, чем об этом написано в знаменитом рассказе классика. Увидев в названии математическую теорию, некоторые из вас сочтут книгу скучной и неинтересной. Ошибаетесь! Пособие написано живо, интересно и очень доступно. Для понимания сути достаточно знаний средней школы. Но несмотря на простой стиль изложения, все утверждения снабжены строгими доказательствами или ссылками на литературу. Круг читателей очень широк: от школьников, интересующихся теорией чисел или шифрованием, до банковских и корпоративных программистов, желающих глубже вникнуть в основы своей деятельности. The Mathematics of Ciphers Number Theory and RSA Cryptography S. С Cojtlnho Department of Computer Science Federalumventty ofRio de Janeiro Rio de Janeiro, Brazil AKPMan NaUck, ManachuMIU © 1999 AK Peters, Ltd. ALL RIGHTS RESERVED © 2001, перевод на русский язык ISBN 5-901095-09-Х «ЗАО Предприятие Постмаркет» Содержание Предисловие 7 Предисловие автора Ю Глава 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 4 Содержание § 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 Содержание 5 § 7. 3.