Факторизация целых чисел

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

История

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

В XVII—XVIII веках Пьер Ферма и Леонард Эйлер разработали первые систематические методы факторизации. Ферма предложил метод, основанный на представлении числа в виде разности квадратов, что эффективно для чисел, близких к квадрату. Эйлер усовершенствовал эти подходы и применил их к числам вида \(a^2 + b^2\).

В XX веке, с развитием вычислительной техники, появились алгоритмы, способные обрабатывать числа с сотнями десятичных знаков. В 1970-х годах был предложен метод квадратичного решета (Померанс, 1981), а в 1990-х — метод решета числового поля (Ленстра, 1993), который остаётся самым быстрым для факторизации чисел общего вида длиной более 100 десятичных цифр.

Классификация алгоритмов

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

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

• Перебор делителей (пробное деление): самый простой метод, при котором проверяется делимость числа на все простые числа до его квадратного корня. Эффективен только для чисел до \(10^{12}\).
• Метод Ферма: основан на поиске таких целых чисел \(x\) и \(y\), что \(N = x^2 - y^2 = (x-y)(x+y)\). Работает хорошо, когда множители близки друг к другу.
• Метод Полларда — Штрассена: использует быстрое умножение матриц и находит множитель за время \(O(N^{1/4} \log N)\).

Вероятностные алгоритмы

• ρ-алгоритм Полларда (1975): основан на парадоксе дней рождения и поиске коллизий в последовательности псевдослучайных чисел. Находит небольшой простой делитель за \(O(N^{1/4})\) операций.
• Метод квадратичного решета (QS): использует свойства квадратичных вычетов и решето для нахождения гладких чисел. Был основным методом для чисел длиной 50–100 цифр до середины 1990-х годов.
• Метод решета числового поля (NFS): самый быстрый для чисел длиной более 100 цифр. Основан на алгебраической теории чисел и использует решето в кольце целых алгебраических чисел. В 2020 году с его помощью было разложено 829-битное число (250 десятичных цифр) в рамках RSA-250.
• Алгоритм Ленстры (эллиптические кривые, ECM): использует группу точек на эллиптической кривой над конечным полем. Особенно эффективен для нахождения средних по размеру простых делителей (до 50–60 цифр).

Применение

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

Сложность факторизации больших чисел (более 600 бит) лежит в основе криптосистемы RSA, которая широко применяется для шифрования данных и цифровых подписей. Безопасность RSA основана на предположении, что разложение произведения двух больших простых чисел на множители требует непрактично большого времени даже для современных компьютеров. Однако развитие квантовых вычислений ставит под угрозу эту парадигму: алгоритм Шора (1994) теоретически позволяет факторизовать любое число за полиномиальное время на квантовом компьютере.

Теория чисел

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

Вычислительная математика

Алгоритмы факторизации встроены во многие математические пакеты (Mathematica, Maple, PARI/GP) и используются для решения задач в алгебре, комбинаторике и теории кодирования.

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

С 1990-х годов проводятся соревнования по факторизации чисел, организованные проектами RSA Factoring Challenge (завершён в 2007 году) и другими. Крупнейшие достижения:

• RSA-240 (795 бит, 240 десятичных цифр): разложен в 2019 году с использованием метода решета числового поля. Потребовалось около 900 ядро-лет на современных процессорах.
• RSA-250 (829 бит, 250 десятичных цифр): разложен в 2020 году той же группой исследователей. Затраты составили около 2700 ядро-лет.
• Факторизация числа 2^1277-1 (385 десятичных цифр): выполнена в 2022 году с помощью метода эллиптических кривых и решета числового поля.

Ограничения и перспективы

Несмотря на прогресс, факторизация чисел длиной более 1024 бит (около 309 десятичных цифр) остаётся практически невозможной для классических компьютеров. Оценки показывают, что для разложения 2048-битного числа потребуется более \(10^{20}\) операций, что превышает возможности существующих вычислительных систем.

В России разработка алгоритмов факторизации ведётся в рамках исследований в области криптографии и теории чисел, в частности в Математическом институте имени В. А. Стеклова РАН и на факультете вычислительной математики и кибернетики МГУ. Российские учёные внесли вклад в развитие метода решета числового поля и его параллельных реализаций.

Критика и альтернативы

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

Источники

• Кнут Д. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2006.
• Ленстра А. К., Ленстра Х. В. Алгоритмы теории чисел // В кн.: Введение в криптографию. — М.: Мир, 1999.
• Pomerance C. A Tale of Two Sieves // Notices of the AMS. — 1996. — Vol. 43, No. 12.
• RSA Factoring Challenge (архив, 2007).
• Математический институт имени В. А. Стеклова РАН. Исследования по теории чисел и криптографии. — М.: МИАН, 2021.