Методы факторизации натуральных чисел
Год: 2011
Автор: Ишмухаметов Ш.Т.
Жанр: Учебное пособие
Издательство: Казань: Казанский ун-т
ISBN: отсутствует
Язык: Русский
Формат: PDF
Качество: Изначально компьютерное (eBook)
Интерактивное оглавление: Нет
Количество страниц: 190
Описание:
Аннотация книги:
Факторизацией натурального числа называется разложение этого числа в произведение простых сомножителей. Эта задача имеет большую вычислительную сложность. Один из самых популярных методов криптографии с открытым ключом, метод RSA, основан на трудоемкости задачи факторизации длинных целых чисел. Другими важными проблемами теории чисел, имеющими важные приложения на практике, являются проблемы проверки простоты целого числа и построения больших простых чисел. В этой книге мы даем описание наиболее известных методов проверки простоты натуральных чисел и факторизации, включая самые быстрые на сегодняшний день метод эллиптических кривых Х. Ленстры, метод квадратичного решета К. Померанца и метод решета числового поля Д. Полларда.
Предназначено для студентов старших курсов факультета вычислительной математики и кибернетики.
Оглавление
Введение
1. Простые числа
1.1. Модулярная арифметика
1.2. Алгоритм быстрого возведения в степень по модулю
1.3. Решето Эратосфена и критерии простоты
1.4. Метод пробных делений
1.5. Решето Аткина
1.6. Тест Поклингтона
1.7. Генерация простых чисел
1.8. Расширенный алгоритм Евклида
1.9. Символ Лежандра
1.10. Тест простоты Миллера–Рабина
1.11. Вероятностный тест простоты Соловея–Штрассена
1.12. Полиномиальный критерий простоты AKS
1.13. Распределение простых чисел
1.14. Извлечение квадратного корня в конечных полях
1.15. Китайская теорема об остатках
1.16. π, e и другие известные константы
1.17. Открытые проблемы теории чисел
1.18. Великая теорема Ферма
1.19. Числа Ферма, Мерсенна и Кармайкла
2. Простые алгоритмы факторизации
2.1. Метод Ферма
2.2. (p - 1)–метод Полларда
2.3. (p + 1)–метод Вильямса
2.4. ρ-метод Полларда
2.5. ρ-метод Полларда для вычисления дискретного логарифма
2.6. Факторизация с использованием непрерывных дробей
2.7. Уравнение Пелла
2.8. Факторизация с использованием квадратичных форм
3. Эллиптические кривые и их приложения в криптографии
3.1. Определение эллиптической кривой
3.2. Число точек эллиптической кривой
3.3. Алгоритм факторизации Ленстры
3.4. Криптографические протоколы на эллиптических кривых
3.5. Спаривание Вейля-Тейта
3.6. Дивизоры
4. Метод квадратичного решета
4.1. Идея Мориса Крейтчика и алгоритм Диксона
4.2. Метод Померанца
4.3. Построение факторной базы
4.4. Решение системы линейных уравнений
4.5. Оценка сложности метода квадратичного решета
4.6. Пример факторизации методом квадратичного решета
4.7. Пример решения системы методом Гаусса
4.8. Вариация множителя в методе квадратичного решета
4.9. Варианты метода квадратичного решета с возможностью распараллеливания
4.10. Метод Занга (Zhang’ Special QS)
5. Метод решета числового поля
5.1. Базовый алгоритм решета числового поля
5.2. Выбор факторных баз
5.3. Просеивание в решете числового поля
5.4. Вычисление квадратного корня
5.5. Пример вычисления квадратного корня и оценка его сложности
5.6. Оценка сложности решета числового поля
5.7. Улучшение алгоритма выбора полиномиальной пары
5.8. Заключение
А. Приложение. Алгебраические числовые поля
А.1. Алгебраические расширения числовых полей
А.2. Идеалы коммутативных колец
А.3. Целые алгебраические числа
А.4. Норма полинома
А.5. Теория делимости в алгебраических числовых полях
Список литературы
Простые числа в криптографии и на трекере
