Разработка и оценка эффективности алгоритмов просеивания для факторизации натуральных чисел

• Автор: Зиятдинов, Дмитрий Булатович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Казань
• Количество страниц: 116 с. : ил.

ОГЛАВЛЕНИЕ
Введение
ГЛАВА 1. Основные алгоритмические этапы методов факторизации
модулей RSA и оценка их сложности
1.1 Квадратичное решето
1.2 Алгоритм решета числового поля
1.3 Экспериментальная оценка сложности алгоритма РЧП
ГЛАВА 2. Методика просеивания по подинтервалам и ее оценка
2.1 Просеивание по подинтевалам в КР
2.1.1 Пример просеивания по подинтервалам в КР
2.1.2 Оценка эффективности просеивания по подинтервалам
2.1.3 Экспериментальная оценка эффективности АПП
2.2 Просеивание по подинтервалам в модификации Занга
2.2.1 Оценка эффективности просеивания по подинтервалам
в модификации Занга
ГЛАВА 3. Методика просеивания по особой области и ее оценка
3.1 Просеивание по особой области в гибридном методе
3.1.1 Оценка сложности гибридного метода
3.2 Эффективный выбор полинома и просеивание по особой области в РЧП
3.2.1 Экспериментальная оценка эффективности просеивания
по особой области в РЧП
ГЛАВА 4. Состав программного комплекса и методика численных экспериментов
4.1 Общие проблемы программной реализации
4.1.1 Генерация полиномов просеивания
4.1.2 Статистическая обработка данных

4.1.3 Некоторые алгоритмы
4.2 Метода Гаусса для систем линейных уравнений большой размерности
4.2.1 Оценки производительности
4.2.2 Пример
4.3 Методика экспериментов
Заключение
Публикации автора
Использованная литература
ПРИЛОЖЕНИЕ А. Дополнительные таблицы и графики
АЛ Просеивание по подинтервалам для КР
ПРИЛОЖЕНИЕ Б. Некоторые исходные тексты программ
Б.1 Генерация сильных чисел RSA
Б.2 Программа для быстрого поиска корней полинома по модулю
простых чисел
Б.З Программа для просеивания по подинтервалам для модификации КР Занга

Список обозначений
В работе используются следующие обозначения:
тг(ті) — Количество простых чисел, не превосходящих п
ір(п) — Количество натуральных чисел, взаимнопростых с п
Ъ/пЪ — Кольцо вычетов, изоморфное целым числам по модулю п
р(и) — Функция Дикмана-Де Брюина (см. [28], стр. 49 и [32])
р|/(.х + кр) — То же, что /(ж + кр) = 0 тосі р р делит /(ж) в точках х + кр
КР — Алгоритм целочисленной факторизации «квадратичное решето»
РЧП — Алгоритм целочисленной факторизации «решето числового поля»

Рис. 1.3. Сравнение оценок сложности алгоритмов КР и РЧП для небольших чисел п
35000 --ЗО'ООО --25000 --20000 --15000

целиком лежит значительно ниже графика 1.1, но более того, меняется сама форма зависимости. Теперь это почти прямая, медленно убывающая с ростом п. Если бы мы посчитали сложность факторизации в этом случае, то убедились бы, что она значительно выше оптимальной. Несмотря на то, что численно этот результат нельзя тривиально продолжить на числа порядка тех, что в реальности используются при факторизации с помощью алгоритма РЧП, это дает хорошее представление о том, насколько сложно оценить в целом эффективность алгоритмов типа КР и РЧП, а также о том, как важно для скорости работы этих алгоритмов хорошо выбрать начальные параметры: полином, радиус просеивания и границу гладкости В.
-т*(п!

>5(п)
29737 44431 57949 70349 82661 94097