Введение в теоретико-числовые методы криптографии, Глухов М.М., Круглов И.А., Пичкур А.Б., Черемушкин А.В., 2011

Введение в теоретико-числовые методы криптографии, Глухов М.М., Круглов И.А., Пичкур А.Б., Черемушкин А.В., 2011.

  Учебное пособие содержит полное изложение материала учебной дисциплины «Теоретико-числовые методы в криптографии» Государственного образовательного стандарта высшего профессионального образования по направлению подготовки «Компьютерная безопасность».
Основу учебного пособия составляют результаты элементарной теории чисел (главы 1-4). В последующих главах рассматривается материал, имеющий многочисленные приложения в современной криптографии: проверка простоты целых чисел, разложение целых чисел на множители, эллиптические кривые, дискретное логарифмирование, теория целочисленных решеток. Особое внимание в пособии уделено алгоритмическим аспектам теории чисел.
Предназначено для студентов вузов, обучающихся по направлениям подготовки в области информационной безопасности, а также для аспирантов.




СЛОЖНОСТЬ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ С ЦЕЛЫМИ ЧИСЛАМИ.
Под алгоритмом обычно понимают четко описанную процедуру решения так называемой массовой задачи, т. е. задачи, состоящей из бесконечного множества конкретных, индивидуальных задач. Ярким примером алгоритма является известный алгоритм Евклида вычисления наибольшего общего делителя целых чисел. В этом случае индивидуальная задача — это задача нахождения НОД для одной фиксированной пары целых чисел. В данном учебном пособии исходными данными алгоритмов будут выступать конечные наборы чисел, записанные в некоторой позиционной (чаще всего двоичной) системе счисления. Сложность алгоритмов будет характеризоваться функцией сложности f(n), аргумент которой п является длиной записи исходных данных алгоритма. При этом для записи функции сложности будет широко применяться О — символика. Целью настоящей главы является подсчет сложности арифметических операций в кольце целых чисел и в кольце вычетов.

Согласно сложившимся традициям алгоритмы делятся на группы по своей сложности:
• полиномиальные алгоритмы, т. е. алгоритмы со сложностью O(nm), m = const;
• экспоненциальные алгоритмы, т. е. алгоритмы со сложностью O(аn), а = const, а > 1.
В дальнейшем будут введены еще так называемые субэкспоненциальные алгоритмы, занимающие промежуточное место.

ОГЛАВЛЕНИЕ.
Введение.
Глава 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.
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. Представление действительных чисел цепными дробями над Z.
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. Метод решета построения B-гладких чисел.
Алгоритм 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.
Список литературы.

Купить .





Теги: учебник по математике :: математика :: Глухов :: Круглов :: Пичкур :: Черемушкин :: криптография