Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Ρ-алгоритм Полларда).pdf

В настоящее время исследования в области построения быстрых алгоритмов факторизации интенсивно проводятся во всем мире. Ежегодно проводятся десятки конференций на эту тему, достигаются новые рекорды факторизации длинных чисел, исследуются известные проблемы алгоритмической теории чисел и ставятся новые задачи. Недавно (в конце 2009 года) группа европейских ученых во главе с Торстеном Кляйнджуном установила новый рекорд разложения 768-битного натурального числа с использованием сита поля чисел. Предыдущий 512-битный рекорд был установлен в 2000 году, то есть переход с 512-битных на 768-битные числа занял почти 10 лет. Поэтому следующую запись в 1024 бита при сохранении той же скорости роста исследования планируется завершить не ранее, чем в 2020 году.

При наличии измерения сложности алгоритмов и информационных структур я обычно говорю о 2 предметах: количестве действий, необходимых для завершения упражнения (вычисляемая сложность), и количестве ресурсов, в частности, памяти, которая необходима для метода ( пластическая сложность).

Алгоритм, который работает в 10 раз быстрее, но применяет в 10 раз больше зон, абсолютно способен приблизиться к назначению серверных машин с огромным объемом памяти.

Однако в интегрированных концепциях, где память уменьшается, этот тип метода не может быть применен.

В данных заметках я побеседуем о трудности вычислений, однако присутствие анализе алгоритмов сортировки я кроме того разберем проблема о ресурсах.

Наша страна практически полностью исключена из участия в этом конкурсе, что объясняется отсутствием источников финансирования таких проектов. Другой причиной является отсутствие в русской литературе самых передовых методов факторизации, таких как метод квадратичного сита и метод численного полевого сита. В отличие от проблемы распознавания простоты числа, факторизация, предположительно, является сложной вычислительной проблемой.

Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории .

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

Сортировка массивов (внутренняя сортировка)

Сортировка последовательных файлов (внешняя сортировка)

Благодаря внутренней сортировке массивы расположены в основной памяти компьютера, что обеспечивает быстрый произвольный доступ к данным.

При внешней сортировке файлы хранятся в «более медленной», но более емкой внешней памяти, то есть на механических запоминающих устройствах (магнитных дисках и других носителях).

Критерии оценки методов сортировки:

количество операций сравнения пар ключей

количество перестановок элементов

экономное использование памяти

Целью написания работы является проведение сравнительного анализа методов факторизации натуральных чисел. В ходе работы были поставлены следующие задачи:

1. Рассмотреть алгоритмы факторизации натуральных чисел;

2. Провести сравнительное описание методов факторизации по группам сложности;

3. Рассмотреть выбранные методы факторизации на практических примерах;

Объектом исследования является выбор методов разложения натуральных чисел.

Предметом являются практические примеры применения метода. В данной работе были рассмотрены следующие методы факторизации натуральных чисел:

Экспоненциальные алгоритмы

- список возможных разделителей

- Метод факторизации фермы

Algorithm-алгоритм Полларда

- метод квадратичных форм Шенкса

- метод Лемана

Субэкспоненциальные алгоритмы

- алгоритм Диксона

Научная формулировка и разработка отдельных аспектов темы исследования отражена в трудах российских ученых и математиков. При написании работы использовалась периодическая учебная литература следующих авторов: Панчишкин А.А., Нестеренко Ю.В., Бухштаб А.А. и так далее.

1. Алгоритмы факторизации натуральных чисел

1.1 Факторизация натурального числа

Натуральное число называется простым, если оно делится только на себя и на 1. Число, не являющееся простым числом, называется составным. Очевидно, что любое простое число, не равное 2, нечетно.

Например, есть знаки деления целых чисел на разные простые числа, так что число в десятичной форме делится на 3 и 9, что достаточно для деления суммы его цифр на 3 и 9 соответственно. Чтобы разделить число на 5, достаточно, чтобы его последняя цифра была 0 или 5. Подобные выборочные свойства делимости возможно применять, в случае если для вас необходимо сократить комплект претендентов с целью контроля несложности либо обозначить сложные количества.

Другим методом извлечения обычных количеств считается ситечко Эратосфена, сваливаемое миксолидийскому научному работнику Эратосфену Киренскому, что проживал приблизительно 276 - 194 вплоть до н.э. Для того чтобы отыскать комплект обычных с целью заранее избранной верхней пределы B, сперва запишите очередность абсолютно всех непарный количеств с 3 вплоть до B. Далее подберите 1-ое количество в перечне, в таком случае имеется первоначальные 3, и забудьте его в list, зачеркните все без исключения сложные 3, включая с 6. Далее переведитесь к 2-ой количеству в перечне (верхняя пять) и зачеркните его многочисленные значимости, сохранив пять и т. д., до тех пока я никак не добьемся окончания перечня. Остальной перечень станет попросту.

Факторизация натурального числа называется его разложением в произведение простых факторов. Существование и единственность (с точностью до порядка факторов) такого разложения вытекает из основной теоремы арифметики.

Эта задача имеет большую вычислительную сложность. Один из самых популярных методов криптографии с открытым ключом, RSA, основан на сложности проблемы факторизации длинных целых чисел.

В данной работе были рассмотрены следующие методы факторизации натуральных чисел:

- экспоненциальные алгоритмы

- список возможных разделителей

- Метод факторизации фермы

Algorithm-алгоритм Полларда

- метод квадратичных форм Шенкса

- метод Лемана

Субэкспоненциальные алгоритмы

- алгоритм Диксона

- метод непрерывной дроби

- метод квадратичного сита

- метод эллиптической кривой

Ситовый номер поля

- метод числового поля специального сита

- Общее количество полей сита

- сложность факторизации

В зависимости от сложности алгоритмы факторизации можно разделить на две группы. Первая группа - это экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входных параметров (то есть от длины самого числа в двоичном представлении). Чтобы указать их сложность, O-обозначение принимается. Это обозначение позволяет рассматривать только наиболее значимые элементы в функции f (n), исключая вторичные.

Например, в функции f (n) = 2n ^ 2-5n 1, если n достаточно велико, компонент n ^ 2 будет значительно превосходить другие члены, и, следовательно, характерное поведение этой функции определяется этим составная часть. Оставшиеся компоненты можно отбросить и условно записать, что эта функция имеет оценку поведения (в смысле скорости роста ее значений) вида O (n ^ 2).

Фраза «алгоритм факторинга с вычислительной сложностью O (N ^ (1⁄2))» означает, что при увеличении параметра N, характеризующего объем входной информации алгоритма, время алгоритма не может быть ограничено растущим значением медленнее, чем N ^ (1 ⁄2).

Вторая группа - это субэкспоненциальные алгоритмы, это алгоритмы, которые работают дольше, чем в полиномиальное время («суперполином»), но меньше, чем в экспоненциальном времени («субэкспоненциальный»). Для обозначения их сложности используется L-обозначение:

где N — число, подлежащее факторизации, и c — некоторые константы.

- Экспоненциальные алгоритмы

Перебор возможных делителей — наиболее тривиальный алгоритм факторизации с вычислительной сложностью .
ρ-алгоритм Полларда имеет сложность ;
метод квадратичных форм Шенкса имеет сложность ;
метод Лемана имеет сложность

- Субэкспоненциальные алгоритмы

алгоритм Диксона имеет сложность ;
метод непрерывных дробей имеет сложность ;
метод квадратичного решета имеет сложность ;
метод эллиптических кривых имеет сложность , где p — наименьшее простое, которое делит N.

Поле номера сита

В настоящее время наиболее эффективными алгоритмами факторизации являются ситовые вариации числового поля:

- специальный метод просеивания числовых полей со сложностью (метод применим только для факторизации чисел специального типа);

- Общее число сит с полем сложности (метод применим ко всем числам).

Все без исключения информационные методы достаточно сложны, в соответствии с этим фактором они вызывают значительные расчетные ресурсы с целью длинных чисел. Однако теоретическое доказательство необходимой проблемы подобных вычислений или, другими словами, существования верхних границ буквы, а также никогда не было доказано, согласно этому фактору, наличия метода факторизации с полиномом. сложность в классическом ЭВМ с целью факторизации - единственные числа

Описание наиболее известных методов факторизации натуральных чисел.зац

ия натуральный число алгоритм

1.2 Перебор делителей

Разделительный перевод (экспериментальное разделение) - это заданный метод для уменьшения или контроля простоты величины посредством абсолютного перечисления абсолютно всех возможных делителей.

Описание алгоритма

Обычно перевод разделителей состоит в перечислении абсолютно всех полных (а также в версии: normal) значений от 2 до квадратного корня из факторизованного числа n и вычислении остатка с использованием d, члена в любой из этих величин. Если превышение деления на определенную величину m равно нулю, то m считается делителем числа n. В этом случае либо n объявляется трудным, и метод завершается (если рассматривается легкость n), либо n уменьшается на m, и процесс повторяется (если n факторизовано). Если квадратный позвоночник достигается с помощью n, и невозможно уменьшить n до 1-го числа с минимальными числами, n должно быть легко прочитано.

Практическое использование

В реальных задачах этот метод используется крайне редко из-за его огромной асимптотической сложности (в O-записи), но его использование целесообразно, если тестируемые величины относительно малы, поскольку этот метод довольно прост в реализации.

1.3 Метод факторизации Ферма

Метод факторизации Ферма - это алгоритм факторизации (факторинга) нечетного целого числа, предложенный Пьером Фармом (1601-1665) в 1643 году.

Этот метод основан на поиске таких целых чисел и , которые удовлетворяют соотношению , что приводит к разложению.

Обоснование

Метод Ферма основан на теореме о представлении числа в виде разности двух квадратов:

Если n>1 нечетно, то существует взаимно однозначное соответствие между разложениями на множители и представлениями в виде разности квадратов с , задаваемое формулами