2-е издание, дополненное. — М.: МЦНМО, 2006. — 335 с. — ISBN
5-94057-103-4
В монографии представлено современное состояние алгоритмической
теории чисел, имеющей важные приложения в криптографии. Во второе
издание внесены исправления и дополнения. К списку литературы
добавлено около 150 новых работ.
Предназначено для студентов старших курсов и аспирантов математических факультетов вузов, а также для специалистов, желающих познакомиться с последними достижениями в данной области.
Содержание: Оглавление
Предисловие
Обозначения
Тестирование чисел на простоту и построение больших простых чисел
Элементарные методы проверки простоты чисел
Тесты на простоту для чисел специального вида
(N±1)-методы проверки простоты чисел и построения больших простых чисел
Алгоритм Конягина-Померанса
Алгоритм Миллера
Вероятностные тесты на простоту
Современные методы проверки простоты чисел
Детерминированный полиномиальный алгоритм проверки простоты чисел
Факторизация целых чисел с экспоненциальной сложностью
Метод Ферма
(Р-1)-метод Полларда
ρ-метод Полларда
Метод Шермана-Лемана
Алгоритм Ленстры
Алгоритм Полларда-Штрассена
(Р+1)-метод Уильямса и его обобщения
Методы Шэнкса
Прочие методы
Факторизация целых чисел с субэкспоненциальной сложностью
Метод Диксона. Дополнительные стратегии
Алгоритм Бриллхарта-Моррисона
Квадратичное решето
Методы Шнорра-Ленстры и Ленстры-Померанса
Алгоритмы решета числового поля
Применение эллиптических кривых для проверки простоты и факторизации целых чисел
Эллиптические кривые и их свойства
Алгоритм Ленстры для факторизации целых чисел с помощью эллиптических кривых
Вычисление порядка группы точек эллиптической кривой над конечным полем
Тестирование чисел на простоту с помощью эллиптических кривых
Алгоритмы дискретного логарифмирования
Детерминированные методы
ρ-метод Полларда для дискретного логарифмирования
Дискретное логарифмирование в простых полях
Дискретное логарифмирование в полях Галуа
Дискретное логарифмирование и решето числового поля
Частное Ферма и дискретное логарифмирование по составному модулю
Факторизация многочленов над конечными полями
Вероятностный алгоритм решения алгебраических уравнений в конечных полях
Решение квадратных уравнений
Алгоритм Берлекэмпа
Метод Кантора-Цассенхауза
Некоторые другие усовершенствования алгоритма Берлекэмпа
Вероятностный алгоритм проверки неприводимости многочленов над конечными полями
Приведенные базисы решеток и их приложения
Решетки и базисы
LLL-приведенный базис и его свойства
Алгоритм построения LLL-приведенного базиса решетки
Алгоритм Шнорра-Ойхнера и целочисленный LLL-алгоритм
Некоторые приложения LLL-алгоритма
Алгоритм Фергюсона-Форкейда
Факторизация многочленов над полем рациональных чисел с полиномиальной сложностью
LLL-алгоритм факторизации: разложение по простому модулю
LLL-алгоритм факторизации: использование решеток
LLL-алгоритм факторизации: подъем разложения
LLL-алгоритм факторизации: полное описание
Практичный алгоритм факторизации
Факторизация многочленов с использованием приближенных вычислений
Дискретное преобразование Фурье и его приложения
Дискретное преобразование Фурье и его свойства
Вычисление дискретного преобразования Фурье
Дискретное преобразование Фурье и умножение многочленов
Дискретное преобразование Фурье и деление многочленов
Применение дискретного преобразования Фурье в алгоритме Полларда-Штрассена
Целочисленная арифметика многократной точности
Сложение и вычитание
Умножение
Деление
Некоторые алгоритмы модулярной арифметики
Решение систем линейных уравнений над конечными полями
Решение систем линейных уравнений в целых числах
Гауссово и структурированное гауссово исключение
Алгоритм Ланцоша
Алгоритм Видемана
Другие методы
Приложение
Сведения из теории чисел
Предназначено для студентов старших курсов и аспирантов математических факультетов вузов, а также для специалистов, желающих познакомиться с последними достижениями в данной области.
Содержание: Оглавление
Предисловие
Обозначения
Тестирование чисел на простоту и построение больших простых чисел
Элементарные методы проверки простоты чисел
Тесты на простоту для чисел специального вида
(N±1)-методы проверки простоты чисел и построения больших простых чисел
Алгоритм Конягина-Померанса
Алгоритм Миллера
Вероятностные тесты на простоту
Современные методы проверки простоты чисел
Детерминированный полиномиальный алгоритм проверки простоты чисел
Факторизация целых чисел с экспоненциальной сложностью
Метод Ферма
(Р-1)-метод Полларда
ρ-метод Полларда
Метод Шермана-Лемана
Алгоритм Ленстры
Алгоритм Полларда-Штрассена
(Р+1)-метод Уильямса и его обобщения
Методы Шэнкса
Прочие методы
Факторизация целых чисел с субэкспоненциальной сложностью
Метод Диксона. Дополнительные стратегии
Алгоритм Бриллхарта-Моррисона
Квадратичное решето
Методы Шнорра-Ленстры и Ленстры-Померанса
Алгоритмы решета числового поля
Применение эллиптических кривых для проверки простоты и факторизации целых чисел
Эллиптические кривые и их свойства
Алгоритм Ленстры для факторизации целых чисел с помощью эллиптических кривых
Вычисление порядка группы точек эллиптической кривой над конечным полем
Тестирование чисел на простоту с помощью эллиптических кривых
Алгоритмы дискретного логарифмирования
Детерминированные методы
ρ-метод Полларда для дискретного логарифмирования
Дискретное логарифмирование в простых полях
Дискретное логарифмирование в полях Галуа
Дискретное логарифмирование и решето числового поля
Частное Ферма и дискретное логарифмирование по составному модулю
Факторизация многочленов над конечными полями
Вероятностный алгоритм решения алгебраических уравнений в конечных полях
Решение квадратных уравнений
Алгоритм Берлекэмпа
Метод Кантора-Цассенхауза
Некоторые другие усовершенствования алгоритма Берлекэмпа
Вероятностный алгоритм проверки неприводимости многочленов над конечными полями
Приведенные базисы решеток и их приложения
Решетки и базисы
LLL-приведенный базис и его свойства
Алгоритм построения LLL-приведенного базиса решетки
Алгоритм Шнорра-Ойхнера и целочисленный LLL-алгоритм
Некоторые приложения LLL-алгоритма
Алгоритм Фергюсона-Форкейда
Факторизация многочленов над полем рациональных чисел с полиномиальной сложностью
LLL-алгоритм факторизации: разложение по простому модулю
LLL-алгоритм факторизации: использование решеток
LLL-алгоритм факторизации: подъем разложения
LLL-алгоритм факторизации: полное описание
Практичный алгоритм факторизации
Факторизация многочленов с использованием приближенных вычислений
Дискретное преобразование Фурье и его приложения
Дискретное преобразование Фурье и его свойства
Вычисление дискретного преобразования Фурье
Дискретное преобразование Фурье и умножение многочленов
Дискретное преобразование Фурье и деление многочленов
Применение дискретного преобразования Фурье в алгоритме Полларда-Штрассена
Целочисленная арифметика многократной точности
Сложение и вычитание
Умножение
Деление
Некоторые алгоритмы модулярной арифметики
Решение систем линейных уравнений над конечными полями
Решение систем линейных уравнений в целых числах
Гауссово и структурированное гауссово исключение
Алгоритм Ланцоша
Алгоритм Видемана
Другие методы
Приложение
Сведения из теории чисел