Введение в теоретико-числовые методы криптографии. Учебное пособие для СПО

Введение
Глава 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.1
Алгоритм 1.2
1.3.3. Использование китайской теоремы об
остатках
Глава 2
Решение уравнений в кольцах вычетов
2.1. Строение мультипликативной группы
кольца вычетов
2.1.1. Критерий цикличности мультипликативной
группы кольца вычетов
2.1.2. Первообразные корни по модулю N
2.2. Решение уравнений в кольцах вычетов
2.2.1. Сведение к простому модулю
2.2.2. Случай простого модуля
Алгоритм 2.1
2.3. Исследование квадратных сравнений.
Квадратичные вычеты и невычеты
Алгоритм 2.2 j
2.4. Решение некоторых типов уравнений в
кольцах вычетов
2.4.1. Извлечение квадратного корня в кольцах
вычетов
Алгоритм 2.3
Алгоритм 2.4
Алгоритм 2.5
Алгоритм 2.6
2.4.2. Извлечение корня в кольцах вычетов
Алгоритм 2.7
Алгоритм 2.8
2.4.3. Показательные сравнения.
Сведение к простому модулю
Глава 3
Цепные дроби
3.1. Представление действительных чисел
цепными дробями
3.1.1. Конечные и бесконечные цепные дроби и их
свойства
3.1.2. Представление действительных чисел
цепными дробями над Ъ
3.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
5.1.2. Тест Соловея-Штрассена
Алгоритм 5.2
5.1.3. Тест Миллера-Рабина
Алгоритм 5.3
5.2. Полиномиальный тест
распознавания простоты
Алгоритм 5.4
5.3. Применение характеров и сумм Гаусса
для проверки простоты целых чисел
Алгоритм 5.5
5.4. Построение больших простых чисел
Алгоритм 5.6
5.4.1. Теорема Поклингтона
5.4.2. Метод Маурера генерации простых чисел
5.4.3. Сильно простые числа
Глава 6
Разложение целых чисел на множители
6.1. Экспоненциальные алгоритмы факторизации
6.1.1. Метод пробных делений
6.1.2. p-метод Полларда
Алгоритм 6.1
Алгоритм 6.2
6.1.3. Метод Ферма
Алгоритм 6.3
6.1.4. (р - 1)-метод Полларда
Алгоритм 6.4
6.1.5. (р + 1)-метод Вильямса
Алгоритм 6.5
6.2. Субэкспоненциальные алгоритмы
факторизации.
6.2.1. Алгоритм Диксона
Алгоритм 6.6
6.2.2. Алгоритм Брил л харта-Моррисона
6.2.3. Метод решета построения В-гладких чисел
Алгоритм 6.7
6.2.4. Метод квадратичного решета
Алгоритм 6.8
Глава 7
Эллиптические кривые
7.1. Эллиптические кривые над конечными полями
Алгоритм 7.1
Алгоритм 7.2
7.2. Эллиптические конфигурации
7.3. Факторизация целых чисел
с помощью эллиптических кривых
Алгоритм 7.3
7.4. Проверка целых чисел на простоту
с помощью эллиптических кривых
Алгоритм 7.4
Глава 8
Методы вычисления дискретных логарифмов
8.1. Алгоритмы дискретного логарифмирования
в произвольной конечной циклической группе
8.1.1. Алгоритм Гельфонда-Шенкса
Алгоритм 8.1
8.1.2. Метод сведения к собственным подгруппам
8.1.3. Метод Сильвера-Полига-Хеллмана
Алгоритм 8.2
8.1.4. p-метод Полларда и его распараллеливание
Алгоритм 8.3
Алгоритм 8.4
8.2. Алгоритмы дискретного логарифмирования
в конечном простом поле
8.2.1. Индекс-метод логарифмирования
в конечном простом поле
Алгоритм8.5
8.2.2, Метод линейного решета
Первый этап метода линейного решета
Алгоритм 8.6
Второй этап метода линейного решета
Алгоритм 8.7
Модификация первого этапа
метода линейного решета
Алгоритм 8.8
8.3. Алгоритмы дискретного логарифмирования
в конечном непростом поле
Алгоритм 8.9
Метод Д. Копперсмита логарифмирования
в полях GF(2n)
Глава 9
Методы геометрии чисел
9.1. Решетки в евклидовом пространстве
9.1.1. Основные определения
9.1.2, Целочисленные решетки и матрицы
Алгоритм 9.1
9.2. Редуцированный по Минковскому базис
решетки
9.2.1. Редуцированный по Минковскому базис
решетки
Алгоритм 9.2
9.2.2. Редукция решеток размерности 2.
Алгоритм Гаусса
Алгоритм 9.3
9.2.3. Редукция решеток размерности 3
Алгоритм 9.4
9.3. Последовательные минимумы.
Теорема Минковского о выпуклом теле
9.3.1. Последовательные минимумы
9.3.2. Теорема Минковского о выпуклом теле
9.4. LLL-алгоритм и его приложения
9.4.1. Алгоритм Ловаца (LLL-алгоритм)
Алгоритм 9.5
9.4.2. Приложения алгоритма Ловаца
1. Вычисление кратчайшего вектора решетки
2. Целочисленное линейное
программирование с ограниченным числом
неизвестных
Алгоритм 9.6
3. Алгоритм Бабаи
Алгоритм 9.7
Список литературы