АЛГОРИТМЫ ФАКТОРИЗАЦИИ ЦЕЛЫХ ЧИСЕЛ С ЭКСПОНЕНЦИАЛЬНОЙ СЛОЖНОСТЬЮ

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

Основные определения

Приведем определения некоторых терминов, использующихся в работе:

Определение 1. Простое число – натуральное число N, большее единицы, которое имеет ровно два различных положительных целых делителя – единицу и самого себя.

Определение 2. Составное число – натуральное число N, которое не является простым.

Определение 3. Факторизация натурального числа – разложение натурального числа N на простые множители.

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

Введение

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

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

Алгоритмы факторизации

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

В данной работе рассматриваются методы с экспоненциальной сложностью.

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

Сложность алгоритма: O – в случае перебора всех простых чисел и O – в случае сложность перебора всех целых чисел.

Описание: алгоритм факторизации числа путем последовательного деления на натуральные числа от 1 до [].

Алгоритм: представлен в виде блок-схемы на рисунке 1.

Рисунок 1. Алгоритм факторизации числа перебором всех простых делителей

Практическое применение: На практике деление осуществляется на простые числа из предварительно составленной таблицы, используется только для факторизации чисел меньших 2¹⁶. Для очень больших чисел не применим ввиду низкой скорости работы.

Алгоритм Ферма

Сложность алгоритма: O(logN)

Описание: Данный алгоритм факторизации впервые был предложен Пьером Ферма в 1643 году. Алгоритм заключается в поиске чисел A и B, таких, что N=A²-B²=(A-B)(A+B). Поиск осуществляется увеличением на 1 A или B, в зависимости от текущего знака разности A²-B²-N. Затем, в случае необходимости, алгоритм рекурсивно продолжает свою работу.

Алгоритм: представлен в виде блок-схемы на рисунке 2.

Рисунок 2. Алгоритм Ферма

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

Алгоритм Полларда-Штрассена

Сложность алгоритма: O(N^1/4log⁴N)

Описание: Алгоритм основан на следующей теореме: пусть z∈N, y=z²{\displaystyle z\in \mathbb {N} ,y=z^{2}}. Тогда для любого натурального числа t наименьший простой делитель числа gcd(t, y!) может быть найден за O(N^1/4log⁴N) {\displaystyle O(z\log ^{2}z\log ^{2}t)} арифметических операций.

Алгоритм: представлен в виде блок-схемы на рисунке 3.

Рисунок 3. Алгоритм Полларда-Штрассена

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

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

Сложность алгоритма: O(N^1/4log⁴N)

Описание: Алгоритм является вероятностным ввиду произвольности выбора элементов в ходе выполнения, зависит только от величины делителя, а не раскладываемого на множители числа N. С помощью этого метода было впервые факторизовано число F₈ = +1 – число Ферма.

Алгоритм: представлен в виде блок-схемы на рисунке 4.

Рисунок 4. P-алгоритм Полларда

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

Заключение

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

Список литературы:

1. Василенко, О. Н. Теоретико-числовые алгоритмы в криптографии Издательство Московского Центра непрерывного математического образования, 2003г. – 326 с.
2. Шнайер, Б.М. Прикладная криптография – ТРИУМФ, 2002. – 816 с.