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