Тема: Сравнительный анализ сложности факторизации алгоритмов целых чисел Выполнила: Дубовицкая Н.В., гр 957 Научный руководитель: Ишмухаметов Ш.Т. - презентация

1 Тема: Сравнительный анализ сложности факторизации алгоритмов целых чисел Выполнила: Дубовицкая Н.В., гр 957 Научный руководитель: Ишмухаметов Ш.Т.

2 Факторизация Задача факторизации целого числа N заключается в нахождении разложения его в произведение простых сомножителей. Сложность решения задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как RSA. На сегодняшний день существует большое количество алгоритмов факторизации, среди которых одним из наиболее быстрых методов является метод квадратичного решета

3 Факторизация 12 декабря 2009 г. T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thome факторизовали 232- значное число методом решета числового поля. Этот результат – рекордный в факторизации целых чисел. Предыдущий рекорд – 9 мая 2005 разложено на множители 200-значное число также с помощью метода решета числового поля

4 Задача Постановка задачи: 1. Исследовать время и эффективность разложения целых чисел методами Полларда и квадратичного решета 2. Выполнить оценки по трудоемкости факторизации для методов Полларда и квадратичного решета

5 Задача Отдельные этапы: 1. Реализация блока формирования факторной базы и тестирование на небольших числах 2. Реализация стадии просеивания 3. Формирование матричной системы и ее решение методом исключений Гаусса 4. Формирование тестового набора натуральных чисел, являющихся произведением двух простых чисел длины от до

6 Метод Полларда «ρ-метод» был предложен Дж. Поллардом в 1975г. Обычно используется для отделения небольших простых делителей факторизуемого числа N. Сложность алгоритма: для вероятность события, состоящего в том, что ρ-метод не найдет нетривиального делителя N за время не превосходит величины Метод Полларда – экспоненциальный алгоритм

7 Метод Полларда Алгоритм 1. Выбираем многочлен 2. Случайно выбираем и, вычисляя значения, переходим на следующий этап 3. Полагаем, что равно ближайшему слева у которого и вычисляем Если 1

8 Метод квадратичного решета Метод квадратичного решета был разработан Карлом Померанцем в 1982г. Используя этот метод, в 1994 году Аткинс, Граф, Лейланд и Ленстра сумели разложить 129-значное число, предложенное создателями RSA. Сложность алгоритма: Алгоритм субэкспоненциальный

9 Метод квадратичного решета Для разложения числа N необходимо найти не менее (k+1) гладкого числа, k – размерность факторной базы). Решая систему уравнений размерности (k+1), получаем пару (A,B), удовлетворяющую условию Затем проверяется условие Если делитель N найден, то алгоритм останавливается, иначе строит следующую пару А, В

10 Метод квадратичного решета Факторная база - это множество простых чисел, ограниченных сверху некоторой константой Числа, полностью раскладываемые в произведение простых делителей из множества F, называются F-гладкими Цель процедуры просеивания – найти достаточное количество пар гладких чисел (A,B), удовлетворяющих:

11 Метод квадратичного решета 1. Формирование факторной базы FB 2. Первое просеивание – элементы FB должны удовлетворять условию 3. Формирование полинома просеивания 4. Найти корни уравнения: 5. Выбрать [-L,L] для x и просеять полином q(x) для