Методы факторизации натуральных чисел

Автор(ы)

Ишмухаметов Ш.Т

Год

2011

Язык

rus

Теги

Математика Программирование

Аннотация

Методы факторизации натуральных чисел Год : 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