Задача факторизации

Задача факторизации (от лат. factor — делающий, производящий) — это задача разложения целого числа на произведение нескольких множителей, обычно на простые числа. В математике факторизация является фундаментальной задачей теории чисел, а в криптографии — основой стойкости многих современных асимметричных криптосистем, таких как RSA.

Определение и постановка задачи

Формально задача факторизации формулируется следующим образом: для данного целого числа \( n \) (обычно составного, большего единицы) найти такое разложение \( n = p_1^{e_1} \cdot p_2^{e_2} \cdot \ldots \cdot p_k^{e_k} \), где \( p_1, p_2, \ldots, p_k \) — простые числа, а \( e_1, e_2, \ldots, e_k \) — натуральные числа (показатели степени). Это разложение называется каноническим представлением числа. Основная сложность задачи заключается в том, что для больших чисел (сотни и тысячи десятичных знаков) не существует эффективного (полиномиального по времени) алгоритма, который гарантированно находит все простые множители.

История

Древние истоки

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

Развитие в XVII–XIX веках

Пьер Ферма (XVII век) предложил метод факторизации, основанный на представлении числа в виде разности квадратов. Леонард Эйлер (XVIII век) разработал метод, использующий свойства квадратичных форм. В XIX веке Карл Фридрих Гаусс в «Арифметических исследованиях» заложил основы современной теории чисел, включая методы факторизации, связанные с квадратичными вычетами.

XX век: от ручных вычислений к компьютерам

До середины XX века факторизация выполнялась вручную или с помощью механических вычислителей. С появлением электронных вычислительных машин (1940-е годы) стали разрабатываться первые алгоритмы, пригодные для автоматизации. В 1970-е годы, с изобретением криптосистемы RSA (Ривест, Шамир, Адлеман, 1977), задача факторизации приобрела огромное практическое значение, так как стойкость RSA основана на предположении о трудности факторизации больших полупростых чисел (произведения двух простых чисел).

Современность

В XXI веке факторизация чисел длиной до 100–150 десятичных знаков считается практически решаемой с помощью мощных вычислительных кластеров и распределённых проектов (например, GIMPS, NFS@Home). Однако числа длиной более 200–300 десятичных знаков остаются недоступными для факторизации за разумное время (тысячи лет на современных компьютерах). В 2020-е годы активно исследуются возможности квантовых компьютеров, которые, согласно алгоритму Шора (1994), могут решать задачу факторизации за полиномиальное время, что потенциально угрожает криптосистемам на основе RSA.

Классификация и виды

По типу чисел

• Факторизация произвольного составного числа — общая задача, не накладывающая ограничений на структуру множителей.
• Факторизация полупростого числа — частный случай, когда число является произведением двух простых чисел. Именно этот тип используется в RSA.
• Факторизация чисел специального вида — например, чисел Мерсенна (\( 2^p - 1 \)), чисел Ферма (\( 2^{2^k} + 1 \)), факториалы и т.д. Для них существуют специализированные алгоритмы.

По методам решения

• Детерминированные алгоритмы — гарантированно находят разложение за конечное время (например, метод пробного деления, метод Ферма, метод Полларда p-1).
• Вероятностные алгоритмы — с высокой вероятностью находят множитель, но не гарантируют результат (например, метод Полларда ρ, метод квадратичного решета, метод решета числового поля).
• Квантовые алгоритмы — используют принципы квантовой механики (алгоритм Шора).

Устройство и характеристики

Основные алгоритмы факторизации

Пробное деление

Самый простой метод: последовательно делить число \( n \) на все простые числа до \( \sqrt{n} \). Время работы — \( O(\sqrt{n}) \), что экспоненциально по длине числа (в битах). Применим только для чисел до \( 10^{12} \) (около 40 бит).

Метод Ферма

Основан на представлении \( n = a^2 - b^2 = (a-b)(a+b) \). Эффективен, если множители близки друг к другу. Время работы — \( O(\sqrt{p}) \), где \( p \) — меньший множитель.

Метод Полларда ρ (ро)

Вероятностный алгоритм, использующий псевдослучайные последовательности и парадокс дней рождения. Время работы — \( O(\sqrt[4]{n}) \) в среднем. Применяется для чисел до \( 10^{20} \) (около 70 бит).

Метод Полларда p-1

Основан на малой теореме Ферма. Эффективен, если один из простых множителей \( p \) таков, что \( p-1 \) состоит из небольших простых делителей. Время работы — \( O(B \log n) \), где \( B \) — граница гладкости.

Метод квадратичного решета (QS)

Один из наиболее эффективных алгоритмов для чисел до 100–120 десятичных знаков. Основан на поиске гладких чисел (чисел, все простые делители которых не превышают заданной границы) и решении системы линейных уравнений. Время работы — \( \exp( (1+o(1)) \sqrt{\log n \log \log n} ) \).

Метод решета числового поля (NFS)

Самый быстрый известный алгоритм для чисел длиной более 100–120 десятичных знаков. Использует алгебраическую теорию чисел. Время работы — \( \exp( (1+o(1)) (\log n)^{1/3} (\log \log n)^{2/3} ) \). Именно с помощью NFS были факторизованы рекордные числа, например, RSA-240 (240 десятичных знаков, 2019 год).

Алгоритм Шора (квантовый)

Квантовый алгоритм, решающий задачу факторизации за полиномиальное время \( O((\log n)^3) \). Требует квантового компьютера с достаточным числом кубитов. На 2025 год квантовые компьютеры не способны факторизовать числа, представляющие практический интерес (например, 2048-битные RSA-ключи).

Сложность

Задача факторизации относится к классу NP (недетерминированно полиномиальные), но не доказано, что она является NP-полной. Предполагается, что она не принадлежит классу P (полиномиальные), то есть не существует алгоритма, решающего её за время, полиномиально зависящее от длины входного числа (в битах). Это предположение лежит в основе стойкости криптосистемы RSA.

Применение

Криптография

• RSA — стойкость основана на трудности факторизации больших полупростых чисел (обычно 2048–4096 бит).
• Криптосистемы на основе эллиптических кривых (ECC) — хотя напрямую не используют факторизацию, задача дискретного логарифмирования на эллиптической кривой также является сложной, и её решение может быть сведено к факторизации в некоторых случаях.
• Атаки на криптосистемы — взлом RSA возможен только при успешной факторизации модуля. Например, атака с помощью метода решета числового поля.

Теория чисел

• Изучение распределения простых чисел, гипотезы Римана, свойства мультипликативных функций.
• Поиск больших простых чисел (например, простых чисел Мерсенна) — важная задача для проверки гипотез и тестирования вычислительных мощностей.

Компьютерная безопасность

• Проверка цифровых подписей, основанных на RSA.
• Анализ стойкости криптографических протоколов (TLS/SSL, SSH, PGP).

Научные вычисления

• Факторизация используется в некоторых алгоритмах решения систем линейных уравнений, в вычислительной алгебре и комбинаторике.
• Распределённые проекты (например, GIMPS, NFS@Home) привлекают добровольцев для факторизации рекордных чисел.

Примеры

Пример 1: Малое число

Факторизация числа 12: \( 12 = 2^2 \cdot 3 \).

Пример 2: Число средней сложности

Факторизация числа 8051:

• Метод пробного деления: проверяем простые числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89. 8051 / 83 = 97, 97 — простое.
• Результат: \( 8051 = 83 \cdot 97 \).

Пример 3: Рекордная факторизация (RSA-240)

В 2019 году международная команда исследователей с помощью метода решета числового поля факторизовала число RSA-240 (240 десятичных знаков, 795 бит). Результат: \( n = p \cdot q \), где \( p \) и \( q \) — простые числа длиной 120 знаков каждое. Затрачено около 900 ядро-лет на этапе решета и 215 ядро-лет на этапе решения линейной системы.

Критика и ограничения

Теоретические ограничения

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

Практические ограничения

• Для чисел длиной более 200–300 десятичных знаков факторизация требует огромных вычислительных ресурсов (сотни тысяч ядро-лет) и времени.
• Распределённые проекты, такие как NFS@Home, могут факторизовать числа до 200–250 знаков, но для чисел длиной 300+ знаков это практически невозможно на современном оборудовании.

Безопасность

• В 2020-е годы стандарты криптографии (например, NIST) рекомендуют использовать RSA-ключи длиной не менее 2048 бит (617 десятичных знаков) для обеспечения безопасности до 2030 года. Для более долгосрочной защиты рекомендуется переход на постквантовую криптографию.

Источники

1. Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007. — Глава 4.5.4.
2. Молдовян Н. А., Молдовян А. А., Еремеев М. А. Криптография: от примитивов к синтезу алгоритмов. — СПб.: БХВ-Петербург, 2004. — Глава 3.
3. Pomerance C., Crandall R. Prime Numbers: A Computational Perspective. — 2nd ed. — Springer, 2005. — Главы 5–7.
4. Shor P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer // SIAM Journal on Computing. — 1997. — Vol. 26, No. 5. — P. 1484–1509.
5. Lenstra A. K., Lenstra H. W. (eds.) The Development of the Number Field Sieve. — Lecture Notes in Mathematics, Vol. 1554. — Springer, 1993.
6. Buhler J. P., Lenstra H. W., Pomerance C. Factoring integers with the number field sieve // The Development of the Number Field Sieve. — Springer, 1993. — P. 50–94.
7. RSA Laboratories. RSA Factoring Challenge. — 1991–2007. — Архивные данные.
8. Kleinjung T. et al. Factorization of a 768-bit RSA modulus // Advances in Cryptology – CRYPTO 2010. — Springer, 2010. — P. 333–350.
9. Friedman J., Pomerance C. Factoring integers with the quadratic sieve // Mathematics of Computation. — 1987. — Vol. 48, No. 177. — P. 183–205.
10. NIST. Post-Quantum Cryptography Standardization. — 2016–2025. — Официальные документы.