Введение в теоретико-числовые методы криптографии
ВВЕДЕНИЕГЛАВА 1. ОЦЕНКА СЛОЖНОСТИ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ1.1. СЛОЖНОСТЬ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ С ЦЕЛЫМИ ЧИСЛАМИ1.1.1. СЛОЖНОСТЬ БАЗОВЫХ ЦЕЛОЧИСЛЕННЫХ АЛГОРИТМОВ1.1.2. БЫСТРЫЕ АЛГОРИТМЫ УМНОЖЕНИЯ ЧИСЕЛ1.1.3. АЛГОРИТМ ВОЗВЕДЕНИЯ В СТЕПЕНЬ1.2. СЛОЖНОСТЬ ВЫЧИСЛЕНИЯ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ ЧИСЕЛ1.2.1. АЛГОРИТМ ЕВКЛИДА НАХОЖДЕНИЯ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ ДВУХ ЧИСЕЛ1.2.2. РАСШИРЕННЫЙ АЛГОРИТМ ЕВКЛИДА1.2.3. ДРУГИЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ1.3. СЛОЖНОСТЬ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ В КОЛЬЦАХ ВЫЧЕТОВ1.3.1. СТАНДАРТНЫЕ АЛГОРИТМЫ1.3.2. АЛГОРИТМ МОНТГОМЕРИ1.3.3. ИСПОЛЬЗОВАНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХГЛАВА 2. РЕШЕНИЕ УРАВНЕНИЙ В КОЛЬЦАХ ВЫЧЕТОВ2.1. СТРОЕНИЕ МУЛЬТИПЛИКАТИВНОЙ ГРУППЫ КОЛЬЦА ВЫЧЕТОВ2.1.1. КРИТЕРИЙ ЦИКЛИЧНОСТИ МУЛЬТИПЛИКАТИВНОЙ ГРУППЫ КОЛЬЦА ВЫЧЕТОВ2.1.2. ПЕРВООБРАЗНЫЕ КОРНИ ПО МОДУЛЮ N2.2. РЕШЕНИЕ УРАВНЕНИЙ В КОЛЬЦАХ ВЫЧЕТОВ2.2.1. СВЕДЕНИЕ К ПРОСТОМУ МОДУЛЮ2.2.2. СЛУЧАЙ ПРОСТОГО МОДУЛЯ2.3. ИССЛЕДОВАНИЕ КВАДРАТНЫХ СРАВНЕНИЙ. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И НЕВЫЧЕТЫ2.4. РЕШЕНИЕ НЕКОТОРЫХ ТИПОВ УРАВНЕНИЙ В КОЛЬЦАХ ВЫЧЕТОВ2.4.1. ИЗВЛЕЧЕНИЕ КВАДРАТНОГО КОРНЯ В КОЛЬЦАХ ВЫЧЕТОВ2.4.2. ИЗВЛЕЧЕНИЕ КОРНЯ В КОЛЬЦАХ ВЫЧЕТОВ2.4.3. ПОКАЗАТЕЛЬНЫЕ СРАВНЕНИЯ. СВЕДЕНИЕ К ПРОСТОМУ МОДУЛЮГЛАВА 3. ЦЕПНЫЕ ДРОБИ3.1. ПРЕДСТАВЛЕНИЕ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ ЦЕПНЫМИ ДРОБЯМИ3.1.1. КОНЕЧНЫЕ И БЕСКОНЕЧНЫЕ ЦЕПНЫЕ ДРОБИ И ИХ СВОЙСТВА3.1.2. ПРЕДСТАВЛЕНИЕ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ ЦЕННЫМИ ДРОБЯМИ НАД Z3.2. ПРЕДСТАВЛЕНИЕ КВАДРАТИЧНЫХ ИРРАЦИОНАЛЬНОСТЕЙ ПЕРИОДИЧЕСКИМИ ЦЕПНЫМИ ДРОБЯМИ3.3. ПРИЛОЖЕНИЯ ЦЕПНЫХ ДРОБЕЙ3.3.1. ПОДХОДЯЩИЕ ДРОБИ КАК НАИЛУЧШИЕ ПРИБЛИЖЕНИЯ3.3.2. ПРИМЕНЕНИЕ ЦЕННЫХ ДРОБЕЙ К РЕШЕНИЮ ЛИНЕЙНЫХ СРАВНЕНИЙ3.3.3. ПРИМЕНЕНИЕ ЦЕПНЫХ ДРОБЕЙ К РЕШЕНИЮ УРАВНЕНИЯ ПЕЛЛЯГЛАВА 4. ПРОСТЫЕ ЧИСЛА4.1. ХАРАКТЕРЫ КОНЕЧНЫХ АБЕЛЕВЫХ ГРУПП И СУММЫ ГАУССА4.1.1. ХАРАКТЕРЫ КОНЕЧНЫХ ПОЛЕЙ И СУММЫ ГАУССА4.1.2. ДОКАЗАТЕЛЬСТВО КВАДРАТИЧНОГО ЗАКОНА ВЗАИМНОСТИ4.1.3. ПРИЛОЖЕНИЕ ХАРАКТЕРОВ И СУММ ГАУССА К НАХОЖДЕНИЮ ОЦЕНОК ЧИСЛА РЕШЕНИЙ УРАВНЕНИЙ НАД КОНЕЧНЫМИ ПОЛЯМИ4.2. РАСПРЕДЕЛЕНИЕ ПРОСТЫХ ЧИСЕЛ В НАТУРАЛЬНОМ РЯДУ4.2.1. ТЕОРЕМА ЧЕБЫШЕВА4.2.2. ПОНЯТИЕ ОБ АНАЛИТИЧЕСКИХ МЕТОДАХ В ТЕОРИИ ЧИСЕЛ4.2.3. ТЕОРЕМА МЕРТЕНСА4.3. КРИТЕРИИ ПРОСТОТЫ. ЧИСЛА ФЕРМА И ЧИСЛА МЕРСЕННА4.3.1. КРИТЕРИИ ПРОСТОТЫ4.3.2. ЧИСЛА ФЕРМА И ЧИСЛА МЕРСЕННАГЛАВА 5. ПРОВЕРКА ПРОСТОТЫ ЦЕЛЫХ ЧИСЕЛ5.1. ВЕРОЯТНОСТНЫЕ ТЕСТЫ ПРОСТОТЫ5.1.1. ТЕСТ ПРОСТОТЫ НА ОСНОВЕ МАЛОЙ ТЕОРЕМЫ ФЕРМА5.1.2. ТЕСТ СОЛОВЕЯ-ШТРАССЕНА5.1.3. ТЕСТ МИЛЛЕРА-РАБИНА5.2. ПОЛИНОМИАЛЬНЫЙ ТЕСТ РАСПОЗНАВАНИЯ ПРОСТОТЫ5.3. ПРИМЕНЕНИЕ ХАРАКТЕРОВ И СУММ ГАУССА ДЛЯ ПРОВЕРКИ ПРОСТОТЫ ЦЕЛЫХ ЧИСЕЛ5.4. ПОСТРОЕНИЕ БОЛЬШИХ ПРОСТЫХ ЧИСЕЛ5.4.1. ТЕОРЕМА ПОКЛИНГТОНА5.4.2. МЕТОД МАУРЕРА ГЕНЕРАЦИИ ПРОСТЫХ ЧИСЕЛ5.4.3. СИЛЬНО ПРОСТЫЕ ЧИСЛАГЛАВА 6. РАЗЛОЖЕНИЕ ЦЕЛЫХ ЧИСЕЛ НА МНОЖИТЕЛИ6.1. ЭКСПОНЕНЦИАЛЬНЫЕ АЛГОРИТМЫ ФАКТОРИЗАЦИИ6.1.1. МЕТОД ПРОБНЫХ ДЕЛЕНИЙ6.1.2. р-МЕТОД ПОЛЛАРДА6.1.3. МЕТОД ФЕРМА6.1.4. (р - 1) - МЕТОД ПОЛЛАРДА6.1.5. (р + 1) - МЕТОД ВИЛЬЯМСА6.2. СУБЭКСПОНЕНЦИАЛЬНЫЕ АЛГОРИТМЫ ФАКТОРИЗАЦИИ6.2.1. АЛГОРИТМ ДИКСОНА6.2.2. АЛГОРИТМ БРИЛЛХАРТА—МОРРИСОНА6.2.3. МЕТОД РЕШЕТА ПОСТРОЕНИЯ В-ГЛАДКИХ ЧИСЕЛ6.2.4. МЕТОД КВАДРАТИЧНОГО РЕШЕТАГЛАВА 7. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ7.1. ЭЛЛИПТИЧЕСКИЕ КРИВЫЕ НАД КОНЕЧНЫМИ ПОЛЯМИ7.2. ЭЛЛИПТИЧЕСКИЕ КОНФИГУРАЦИИ7.3. ФАКТОРИЗАЦИЯ ЦЕЛЫХ ЧИСЕЛ С ПОМОЩЬЮ ЭЛЛИПТИЧЕСКИХ КРИВЫХ7.4. ПРОВЕРКА ЦЕЛЫХ ЧИСЕЛ НА ПРОСТОТУ С ПОМОЩЬЮ ЭЛЛИПТИЧЕСКИХ КРИВЫХГЛАВА 8. МЕТОДЫ ВЫЧИСЛЕНИЯ ДИСКРЕТНЫХ ЛОГАРИФМОВ8.1. АЛГОРИТМЫ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В ПРОИЗВОЛЬНОЙ КОНЕЧНОЙ ЦИКЛИЧЕСКОЙ ГРУППЕ8.1.1. АЛГОРИТМ ГЕЛЬФОНДА-ШЕНКСА8.1.2. МЕТОД СВЕДЕНИЯ К СОБСТВЕННЫМ ПОДГРУППАМ8.1.3. МЕТОД СИЛЬВЕРА-ПОЛИГА-ХЕЛЛМАНА8.1.4. Р-МЕТОД ПОЛЛАРДА И ЕГО РАСПАРАЛЛЕЛИВАНИЕ8.2. АЛГОРИТМЫ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОНЕЧНОМ ПРОСТОМ ПОЛЕ8.2.1. ИНДЕКС-МЕТОД ЛОГАРИФМИРОВАНИЯ В КОНЕЧНОМ ПРОСТОМ ПОЛЕ8.2.2. МЕТОД ЛИНЕЙНОГО РЕШЕТАПЕРВЫЙ ЭТАП МЕТОДА ЛИНЕЙНОГО РЕШЕТАВТОРОЙ ЭТАП МЕТОДА ЛИНЕЙНОГО РЕШЕТАМОДИФИКАЦИЯ ПЕРВОГО ЭТАПА МЕТОДА ЛИНЕЙНОГО РЕШЕТА8.3. АЛГОРИТМЫ ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОНЕЧНОМ НЕПРОСТОМ ПОЛЕМЕТОД Д. КОППЕРСМИТА ЛОГАРИФМИРОВАНИЯ В ПОЛЯХ GF(2n)ГЛАВА 9. МЕТОДЫ ГЕОМЕТРИИ ЧИСЕЛ9.1. РЕШЕТКИ В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ9.1.1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ9.1.2. ЦЕЛОЧИСЛЕННЫЕ РЕШЕТКИ И МАТРИЦЫ9.2. РЕДУЦИРОВАННЫЙ ПО МИНКОВСКОМУ БАЗИС РЕШЕТКИ9.2.1. РЕДУЦИРОВАННЫЙ ПО МИНКОВСКОМУ БАЗИС РЕШЕТКИ9.2.2. РЕДУКЦИЯ РЕШЕТОК РАЗМЕРНОСТИ 2. АЛГОРИТМ ГАУССА.9.2.3. РЕДУКЦИЯ РЕШЕТОК РАЗМЕРНОСТИ 39.3. ПОСЛЕДОВАТЕЛЬНЫЕ МИНИМУМЫ. ТЕОРЕМА МИНКОВСКОГО О ВЫПУКЛОМ ТЕЛЕ9.3.1. ПОСЛЕДОВАТЕЛЬНЫЕ МИНИМУМЫ9.3.2. ТЕОРЕМА МИНКОВСКОГО О ВЫПУКЛОМ ТЕЛЕ9.4. LLL-АЛГОРИТМ И ЕГО ПРИЛОЖЕНИЯ9.4.1. АЛГОРИТМ ЛОВАЦА (LLL-АЛГОРИТМ)9.4.2. ПРИЛОЖЕНИЯ АЛГОРИТМА ЛОВАЦАВЫЧИСЛЕНИЕ КРАТЧАЙШЕГО ВЕКТОРА РЕШЕТКИЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ С ОГРАНИЧЕННЫМ ЧИСЛОМ НЕИЗВЕСТНЫХАЛГОРИТМ БАБАИСПИСОК ЛИТЕРАТУРЫ
