Читать онлайн «Теоретико-числовые методы в криптографии учебное пособие»

А. Ю. Нестеренко ТЕОРЕТИКО-ЧИСЛОВЫЕ МЕТОДЫ В КРИПТОГРАФИИ Москва 2012 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный институт электроники и математики (технический университет) А. Ю. НЕСТЕРЕНКО Теоретико-числовые методы в криптографии Рекомендовано Редакционно-издательским советом института в качестве учебного пособия Москва 2012 УДК 511 Рецензенты: докт. физ. - мат. наук, проф. В. Г. Данилов, зав. кафедрой математического анализа МТУСИ; докт. физ. - мат. наук, проф. В. Г. Чирский, зав. кафедрой теории чисел математического факультета МПГУ. Нестеренко А. Ю. Теоретико-числовые методы в криптографии: учебное пособие. Моск. гос. ин-т. электроники и математики. 2012, 224 с. ISBN 978-5-94506-320-4 Изложен курс алгоритмической теории чисел с приложениями. Основное внимание уделено вопросам строгого обоснования, эффективной реализации и анализа трудоемкости алгоритмов, используемых в криптографических приложениях. Рассматриваются вопросы решения некоторых диофантовых уравнений, вопросы решения сравнений произвольных степеней по простому и составному модулям, а также методы доказательства простоты и построения больших простых чисел, методы решения задач дискретного логарифмирования и разложения больших целых чисел на множители. Предназначено студентам старших курсов МИЭМ, обучающимся по специальности «Компьютерная безопасность». ISBN 978-5-94506-320-4 УДК 511 © А. Ю. Нестеренко, 2012. © Московский государственный институт электроники и математики, 2012. Оглавление Оглавление 3 Введение б 1 Элементарная теория делимости 11 1. 1 Наибольший общий делитель 12 1. 2 Алгоритм Эвклида 13 1. 3 Простые числа 17 2 Сравнения 21 2. 1 Сравнения первой степени 22 2. 2 Китайская теорема об остатках 25 2. 3 Функция Эйлера 29 2. 4 Первообразные корни 32 2. 4. 1 Первообразные корни по модулю простого числа ρ 34 2. 4. 2 Первообразные корни по модулю ра 39 2. 5 Алгебраическое отступление 42 3 Многочлены 44 3. 1 Элементарные операции 44 3. 2 Алгоритм Эвклида для многочленов 48 3. 3 Основная теорема арифметики для многочленов 51 3. 4 Дифференцирование многочленов 55 3. 5 Решение сравнений по составному модулю 56 4 Сравнения старших степеней 61 4. 1 Квадратичные вычеты 61 4. 2 Символ Якоби 69 4. 3 Вычисление квадратного корня 74 4. 4 Вероятностный алгоритм вычисления корней многочленов 82 5 Непрерывные дроби 87 5. 1 Конечные непрерывные дроби 88 5. 2 Понятие подходящей дроби 89 5. 3 Квадратичные иррациональности 94 5. 4 Наилучшие приближения 105 3 Оглавление 4 6 Простые числа 109 6. 1 Вероятностные тесты проверки простоты 111 6. 1. 1 Тест Соловея-Штрассена 114 6. 1. 2 Тест Миллера-Рабина 117 6. 2 N — 1 методы доказательства простоты 122 6. 3 N + 1 метод доказательства простоты 127 6. 4 Алгоритмы построения простых чисел 134 6. 4. 1 Рекурсивный алгоритм построения простых по известному разложению ρ — 1 135 6. 4. 2 Алгоритм построения сильно простого числа ... . 138 7 Факторизация целых чисел 142 7. 1 Метод пробного деления 142 7. 2 Метод Ферма 143 7. 2. 1 Вычисление квадратного корня 144 7. 2. 2 Как быстро проверить, что число является полным квадратом 145 7. 3 Метод Лемана 149 7. 4 Метод Полларда-Флойда 152 7. 5 Метод Брента 154 7. 6 ρ — 1 метод Полларда 155 7. 7 ρ + 1 метод Вильямса 157 7. 8 Оптимизация алгоритмов Полларда и Вильямса 159 7. 8. 1 Разностная схема 160 7. 8. 2 Метод согласования 161 7. 8. 3 Поиск пар простых чисел 162 7. 8. 4 Поиск циклов в последовательностях 163 7. 9 Метод Женга 164 7. 10 Метод Макки 167 8 Факторизация целых чисел II 172 8. 1 Метод Крайчика 173 8. 2 Метод непрерывных дробей 174 8. 2. 1 Первый вариант 175 8. 2. 2 Второй вариант 177 8. 2. 3 Метод Моррисона и Бриллхарта 178 8. 2. 4 Как выбрать множитель к 180 8. 2. 5 Как выбрать квадратичную иррациональность . . . 183 8. 2. 6 Заключение 185 8. 3 Метод линейного решета 186 Оглавление 5 8. 4 Метод квадратичного решета 188 8. 4. 1 MPQS - метод нескольких многочленов 190 9 Дискретное логарифмирование 194 9. 1 Метод согласования 196 9. 2 Логарифмирование в подгруппе составного порядка ... . 198 9. 3 Вероятностные методы 203 9. 3. 1 Метод Полларда-Флойда 203 9. 3. 2 Метод Госпера 205 9. 4 Субэкспоненциальный метод 207 9. 4. 1 Идеология Крайчика 208 9. 4. 2 Алгоритм Адлемана 210 9. 4. 3 Решение систем линейных сравнений 212 9. 4. 4 Асимптотическая оценка метода 217 Литература 219 Введение Настоящее учебное пособие содержит в себе изложение вопросов элементарной алгоритмической теории чисел.