Теоретико-числовые алгоритмы в криптографии, Василенко О.Н., 2003

Теоретико-числовые алгоритмы в криптографии, Василенко О.Н., 2003.

   В монографии представлено современное состояние алгоритмической теории чисел, имеющей важные приложения в криптографии.
Предназначено для студентов старших курсов и аспирантов математических факультетов вузов, а также для специалистов, желающих познакомиться с последними достижениями в данной области.




Современные методы проверки простоты чисел.
В начале 80-х годок Адлеман, Померане и Румели предложили детерминированный алгоритм проверки простоты чисел. Для заданного натурального числа n алгоритм делает О((lоg n)c lоg lоg lоg n) арифметических операций (с — некоторая абсолютная постоянная) и выдает верный ответ, составное n или простое. Описание схемы алгоритма можно найти также в [10]. Этот алгоритм оказался непрактичным и довольно сложным для реализации на компьютере.

Существенные теоретические упрощения алгоритма Адлемана—Померанса—Румели были получены Х. Ленстрой. Он предложил детерминированный алгоритм, также делающий O((log n)c lоg lоg lоg n) арифметических операций. Реализация этого алгоритма позволила проверять на простоту числа п порядка 10100 за несколько минут.

ОГЛАВЛЕНИЕ.
Предисловие.
Обозначения.
Глава 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. (Р — 1)-метод Полларда.
§2.3. p-метод Полларда.
§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. Другие методы. Заключение.
Приложение. Сведения из теории чисел.
Литература.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Теоретико-числовые алгоритмы в криптографии, Василенко О.Н., 2003 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Хештеги: #учебник по математике :: #математика :: #Василенко :: #алгоритм :: #криптография