Теоретико-числовые алгоритмы в криптографии

Титульный лист
Выходные данные
Оглавление
Предисловие
Предисловие ко второму изданию
Обозначения
Глава 1. Тестирование чисел на простоту и построение больших простых чисел
	§ 1.1. Введение
	§ 1.2. Элементарные методы проверки простоты чисел
	§ 1.3. Тесты на простоту для чисел специального вида
	§ 1.4. (N±1)-методы проверки простоты чисел и построения больших простых чисел
	§ 1.5. Алгоритм Конягина—Померанса
	§ 1.6. Алгоритм Миллера
	§ 1.7. Вероятностные тесты на простоту
	§ 1.8. Современные методы проверки простоты чисел
	§ 1.9. Заключение. Детерминированный полиномиальный алгоритм проверки простоты чисел
Глава 2. Факторизация целых чисел с экспоненциальной сложностью
	§ 2.1. Введение. Метод Ферма
	§ 2.2. (P-1)-метод Полларда
	§ 2.3. ρ-метод Полларда
	§ 2.4. Метод Шермана—Лемана
	§ 2.5. Алгоритм Ленстры
	§ 2.6. Алгоритм Полларда—Штрассена
	§ 2.7. (Р+1)-метод Уильямса и его обобщения
	§ 2.8. Методы Шэнкса
	§ 2.9. Прочие методы. Заключение
Глава 3. Факторизация целых чисел с субэкспоненциальной сложностью
	§ 3.1. Введение
	§ 3.2. Метод Диксона. Дополнительные стратегии
	§ 3.3. Алгоритм Бриллхарта—Моррисона
	§ 3.4. Квадратичное решето
	§ 3.5. Методы Шнорра—Ленстры и Ленстры—Померанса
	§ 3.6. Алгоритмы решета числового поля
	§ 3.7. Заключение
Глава 4. Применение эллиптических кривых для проверки простоты и факторизации целых чисел
	§ 4.1. Введение. Эллиптические кривые и их свойства
	§ 4.2. Алгоритм Ленстры для факторизации целых чисел с помощью эллиптических кривых
	§ 4.3. Вычисление порядка группы точек эллиптической кривой над конечным полем
	§ 4.4. Тестирование чисел на простоту с помощью эллиптических кривых
	§ 4.5. Заключение
Глава 5. Алгоритмы дискретного логарифмирования
	§ 5.1. Введение. Детерминированные методы
	§ 5.2. ρ-метод Полларда для дискретного логарифмирования
	§ 5.3. Дискретное логарифмирование в простых полях
	§ 5.4. Дискретное логарифмирование в полях Галуа
	§ 5.5. Дискретное логарифмирование и решето числового поля
	§ 5.6. Частное Ферма и дискретное логарифмирование по составному модулю
	§ 5.7. Заключение
Глава 6. Факторизация многочленов над конечными полями
	§ 6.1. Введение. Вероятностный алгоритм решения алгебраических уравнений в конечных полях
	§ 6.2. Решение квадратных уравнений
	§ 6.3. Алгоритм Берлекэмпа
	§ 6.4. Метод Кантора—Цассенхауза
	§ 6.5. Некоторые другие усовершенствования алгоритма Берлекэмпа
	§ 6.6. Вероятностный алгоритм проверки неприводимости многочленов над конечными полями
	§ 6.7. Заключение
Глава 7. Приведенные базисы решеток и их приложения
	§ 7.1. Введение. Решетки и базисы
	§ 7.2. LLL-приведенный базис и его свойства
	§ 7.3. Алгоритм построения LLL-приведенного базиса решетки
	§ 7.4. Алгоритм Шнорра—Ойхнера и целочисленный LLL-алгоритм
	§ 7.5. Некоторые приложения LLL-алгоритма
	§ 7.6. Алгоритм Фергюсона—Форкейда
	§ 7.7. Заключение
Глава 8. Факторизация многочленов над полем рациональных чисел с полиномиальной сложностью
	§ 8.1. Введение
	§ 8.2. LLL-алгоритм факторизации: разложение по простому модулю
	§ 8.3. LLL-алгоритм факторизации: использование решеток
	§ 8.4. LLL-алгоритм факторизации: подъем разложения
	§ 8.5. LLL-алгоритм факторизации: полное описание
	§ 8.6. Практичный алгоритм факторизации
	§ 8.7. Факторизация многочленов с использованием приближенных вычислений
	§ 8.8. Заключение
Глава 9. Дискретное преобразование Фурье и его приложения
	§ 9.1. Введение. Дискретное преобразование Фурье и его свойства
	§ 9.2. Вычисление дискретного преобразования Фурье
	§ 9.3. Дискретное преобразование Фурье и умножение многочленов
	§ 9.4. Дискретное преобразование Фурье и деление многочленов
	§ 9.5. Применение дискретного преобразования Фурье в алгоритме Полларда—Штрассена
	§ 9.6. Заключение
Глава 10. Целочисленная арифметика многократной точности
	§ 10.1. Введение. Сложение и вычитание
	§ 10.2. Умножение
	§ 10.3. Деление
	§ 10.4. Некоторые алгоритмы модулярной арифметики
Глава 11. Решение систем линейных уравнений над конечными полями
	§ 11.1. Введение
	§ 11.2. Решение систем линейных уравнений в целых числах
	§ 11.3. Гауссово и структурированное гауссово исключение
	§ 11.4. Алгоритм Ланцоша
	§ 11.5. Алгоритм Видемана
	§ 11.6. Другие методы. Заключение
Приложение. Сведения из теории чисел
Литература
Предметный указатель