Задача факторизации целых чисел¶

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

¶История

¶Ранние методы

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

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

В 1643 году французский математик Пьер Ферма предложил метод факторизации, основанный на представлении числа в виде разности квадратов (метод Ферма). Этот метод эффективен, если два множителя числа близки друг к другу. В 1770 году Эйлер разработал метод, использующий квадратичные формы. В XIX веке были созданы таблицы простых чисел и делителей, например, таблицы Карла Фридриха Гаусса, которые облегчали факторизацию вручную.

¶XX век и появление компьютеров

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

¶Современный этап

В 1990-х годах были созданы алгоритмы, такие как метод квадратичного решета (QS) и метод решета числового поля (NFS), которые позволили разлагать числа длиной до 100–200 десятичных знаков. В 2009 году было разложено 232-значное число RSA-768 (768 бит) с использованием NFS, что потребовало около двух лет вычислений на кластере из сотен компьютеров. В 2020-х годах прогресс в квантовых вычислениях поставил под вопрос долгосрочную стойкость RSA, поскольку алгоритм Шора теоретически позволяет факторизовать числа за полиномиальное время на квантовом компьютере.

¶Математическая постановка

Задача факторизации формулируется следующим образом: для данного целого числа \( n > 1 \) найти все простые числа \( p_i \) и их степени \( e_i \), такие что \( n = \prod_{i=1}^k p_i^{e_i} \). Если \( n \) простое, то факторизация тривиальна — это само число. В общем случае, сложность задачи возрастает с ростом \( n \), особенно если \( n \) является произведением двух больших простых чисел примерно одинакового размера (как в RSA).

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

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

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

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

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

¶Метод Ферма

Основан на представлении \( n = a^2 - b^2 = (a-b)(a+b) \). Алгоритм ищет целое \( a \), такое что \( a^2 - n \) является полным квадратом. Эффективен, когда множители близки, но в худшем случае имеет сложность \( O(n) \).

¶ρ-алгоритм Полларда

Разработан Джоном Поллардом в 1975 году. Использует вероятностный подход: генерирует последовательность чисел с помощью псевдослучайной функции и ищет коллизии по модулю делителя. Сложность — \( O(n^{1/4}) \) в среднем. Подходит для чисел до 10^20–10^30.

¶(p-1)-метод Полларда

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

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

Разработан Карлом Померансом в 1981 году. Является развитием метода факторизации с помощью разности квадратов. Ищет пары чисел \( x \) и \( y \), такие что \( x^2 \equiv y^2 \pmod{n} \), что даёт множитель. Сложность — \( O(e^{(1+o(1))\sqrt{\ln n \ln \ln n}}) \). Был рекордным для чисел до 100 десятичных знаков.

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

Наиболее эффективный алгоритм для больших чисел (более 100 десятичных знаков). Разработан в 1990-х годах. Использует алгебраическую теорию чисел и работает в кольцах целых алгебраических чисел. Сложность — \( O(e^{(1.923+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}) \). Именно с помощью NFS были разложены рекордные числа RSA.

¶Квантовые алгоритмы

В 1994 году Питер Шор предложил квантовый алгоритм факторизации, который работает за полиномиальное время \( O((\log n)^3) \). Алгоритм использует квантовое преобразование Фурье для нахождения периода функции. На 2025 год квантовые компьютеры способны факторизовать лишь небольшие числа (например, 21 = 3×7), но прогресс в этой области может сделать RSA уязвимым в будущем.

¶Сложность и рекорды

¶Теоретическая сложность

Наилучший известный классический алгоритм (NFS) имеет субэкспоненциальную сложность, что означает, что время решения растёт быстрее любого полинома, но медленнее экспоненты. Для чисел длиной 1024 бита (около 309 десятичных знаков) оценка времени на современном оборудовании составляет миллионы лет. Для чисел длиной 2048 бита (617 десятичных знаков) — практически бесконечно.

¶Рекорды факторизации

• 1991 год: разложение числа RSA-129 (129 десятичных знаков) методом квадратичного решета за 8 месяцев.
• 1999 год: разложение 155-значного числа RSA-155 методом NFS.
• 2009 год: разложение 232-значного числа RSA-768 (768 бит) с использованием NFS на кластере из сотен компьютеров.
• 2020 год: разложение 250-значного числа RSA-250 (829 бит) с помощью NFS.

На 2025 год рекордным является разложение числа длиной 829 бит (RSA-250). Числа длиной 1024 бита и более пока не поддаются факторизации.

¶Применение

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

Основное применение задачи факторизации — обеспечение безопасности криптосистемы RSA. Стойкость RSA основана на предположении, что факторизация произведения двух больших простых чисел (размером 1024–4096 бит) вычислительно невозможна за разумное время. Если факторизация станет возможной, RSA будет скомпрометирована.

¶Другие области

• Теория чисел: факторизация используется для изучения свойств чисел, например, в распределении простых чисел.
• Алгоритмы: факторизация применяется в некоторых алгоритмах хеширования и генерации псевдослучайных чисел.
• Квантовые вычисления: задача факторизации служит эталоном для демонстрации квантового превосходства.

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

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

¶Интересные факты

• В 1977 году создатели RSA предложили факторизовать 129-значное число (RSA-129) за премию в 100 долларов. Задача была решена только в 1994 году.
• Алгоритм Шора вдохновил развитие квантовых компьютеров: многие исследователи считают, что именно факторизация станет первой практически значимой задачей, решённой на квантовом компьютере.
• В 2024 году китайские учёные заявили о факторизации 48-битного числа на квантовом компьютере с 10 кубитами, но это не является прорывом, так как классические алгоритмы справляются с такими числами мгновенно.

¶Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007.
• Шнайер Б. Прикладная криптография. — 2-е изд. — М.: Триумф, 2002.
• Pomerance C. A Tale of Two Sieves // Notices of the AMS. — 1996. — Vol. 43, No. 12.
• Lenstra A. K., Lenstra H. W. The Development of the Number Field Sieve. — Springer, 1993.
• 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.