Введение
Глава 1. Основные алгоритмические этапы методов факторизации модулей RSA и оценка их сложности 15
1.1 Квадратичное решето 15
1.2 Алгоритм решета числового поля 24
1.3 Экспериментальная оценка сложности алгоритма РЧП . 29
Глава 2. Методика просеивания по подинтервалам и ее оценка 37
2.1 Просеивание по подинтевалам в КР 37
2.1.1 Пример просеивания по подинтервалам в КР 39
2.1.2 Оценка эффективности просеивания по подинтервалам. 41
2.1.3 Экспериментальная оценка эффективности АПП . 44
2.2 Просеивание по подинтервалам в модификации Занга 49
2.2.1 Оценка эффективности просеивания по подинтервалам в модификации Занга 52
Глава 3. Методика просеивания по особой области и ее оценка . 56
3.1 Просеивание по особой области в гибридном методе 56
3.1.1 Оценка сложности гибридного метода 61
3.2 Эффективный выбор полинома и просеивание по особой области в РЧП 64
3.2.1 Экспериментальная оценка эффективности просеивания по особой области в РЧП 67
Глава 4. Состав программного комплекса и методика численных экспериментов 70
4.1 Общие проблемы программной реализации 70
4.1.1 Генерация полиномов просеивания 74
4.1.2 Статистическая обработка данных 75
4.1.3 Некоторые алгоритмы 75
4.2 Метода Гаусса для систем линейных уравнений большой размерности 78
4.2.1 Оценки производительности 80
4.2.2 Пример 83
4.3 Методика экспериментов 85
Заключение 87
Публикации автора 88
Использованная литература 88
Приложение А. Дополнительные таблицы и графики 95
А.1 Просеивание по подинтервалам для КР 95
Приложение Б. Некоторые исходные тексты программ 101
Б.1 Генерация сильных чисел RSA 101
Б.2 Программа для быстрого поиска корней полинома по модулю простых чисел 103
Б.3 Программа для просеивания по подинтервалам для модификации КР Занга 109
