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

Введение и основные понятия

Факторизация целого числа — это разложение числа на множители, которые обычно требуются простыми. В общем виде задача состоит в том, чтобы для заданного положительного числа $N \in \mathbb{Z},\ N>1$ найти такие целые числа, что их произведение равно этому числу. В криптографии и теории чисел задача факторизации играет ключевую роль, так как безопасность многих протоколов основана на трудности разложения больших чисел на простые множители.

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

Простой делитель - простой множитель числа, то есть простой элемент в разложении числа на простые множители.

В зависимости от размера и структуры исходного числа применяются разные алгоритмы: от простых «грубых» методов до продвинутых подэкспоненциальных схем. В этом конспекте мы рассмотрим несколько подходов: метод пробного деления, метод Ферма, алгоритм Полларда Ро, метод p-1 Полларда, квадратичную решетку (в общих чертах) и краткое введение в метод на эллиптических кривых.

Метод пробного деления

Метод пробного деления — самый простой и интуитивный. Идея заключается в том, чтобы последовательно делить число $N \in \mathbb{Z},\ N>1$ на простые числа, начиная с наименьших, пока не найдутся ненулевые делители. Этот метод гарантированно найдет фактор, если число невелико или имеет небольшой наименьший простой делитель.

Достаточно проверять делители до значения $\lfloor \sqrt{N} \rfloor$, потому что если у числа нет делителей меньше либо равных этому корню, то число либо простое, либо имеет пару делителей, один из которых больше корня, а другой — меньше. При каждом шаге нужно вычислять остаток от деления и при обнаружении остатка ноль фиксировать найденный множитель.

Сложность метода пробного деления экспоненциально растёт с длиной входа: в простейшей оценке требуется порядка $O(\sqrt{N})$ арифметических операций, поэтому метод применим только для чисел невеликой битовой длины или в качестве предварительного шага в более сложных алгоритмах.

Метод Ферма

Метод Ферма основан на представлении числа в виде разности квадратов: найти числа a и b такие, что $a^2 - b^2 = N$. Тогда очевидно, что $a^2 - b^2 = N$ раскладывается как разность квадратов в виде произведения двух скобок, что приводит к факторизации числа.

Практический алгоритм начинается с вычисления целого a, равного округлению вверх квадратного корня числа: $a = \lceil \sqrt{N} \rceil$. Затем проверяют, является ли $a^2 - b^2 = N$ полным квадратом; если нет, увеличивают a и повторяют процедуру. Метод особенно эффективен, когда число имеет два близких простых множителя, то есть когда представление в виде разности квадратов находится быстро.

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

Алгоритм Полларда Ро

Поллард Ро — вероятностный алгоритм, который часто находит нетривиальный делитель за время существенно меньшее, чем пробное деление для многих практических случаев. Основная идея — использовать псевдослучайную итерацию по кольцу вычетов по модулю $N \in \mathbb{Z},\ N>1$ с функцией вида $f(x)=x^2+c\pmod{N}$ и периодически вычислять величину $d=\gcd(|x-y|,N)$ для обнаружения ненулевого делителя.

Алгоритм использует детектор циклов (например, метод Флойда) для получения двух последовательностей $x_{i+1}=f(x_i)$ с разной скоростью продвижения. При удачном выборе константы c и начального значения вероятность обнаружить делитель довольно высока, а среднее время работы асимптотически оценивается приблизительно как $O(N^{1/4})$, что делает метод пригодным для чисел средней величины.

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

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

Метод p-1 эффективен, когда у числа $N \in \mathbb{Z},\ N>1$ есть простой делитель p такой, что p-1 состоит только из малых простых множителей. Алгоритм строится на выборке основания a и вычислении степени a в большой степенной степени M, часто выбираемой как $M = \mathrm{lcm}(1,\dots,B)$; затем проверяют условие $a^M \equiv 1 \pmod{p}$ по модулю p и вычисляют d по формуле $d = \gcd(a^M - 1, N)$.

Если d — нетривиальный делитель числа, задача решена. Иначе можно увеличить параметр границы или выбрать другое основание a и повторить попытку. Этот метод особенно полезен для чисел, у которых есть простой фактор с «гладким» p-1.

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

Квадратичная решётка (краткий обзор)

Квадратичная решётка, в числе её реализаций — квадратичный сито, является одним из наиболее мощных алгоритмов факторизации для чисел средней и большой величины. Общая идея заключается в поиске набора чисел x_i таких, что их квадраты по модулю N дают значения, которые факторизуются по выбранному базису малых простых (т.е. являются B-гладкими): $x^2 \equiv y \pmod{N}$.

Собрав достаточное количество таких соотношений, строят булеву линейную систему по модулю два, где каждая строка соответствует вектору чётностей степеней простых в факторизации значения y_i. Цель — найти ненулевую комбинацию строк, дающую нулевой вектор по модулю два, т.е. когда сумма векторов эквивалентна нулю $\text{векторная сумма} \equiv 0 \pmod{2}$. Это приводит к квадрату по модулю и, при удаче, к нетривиальному делителю числа.

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

Метод эллиптических кривых (ECM)

Метод на эллиптических кривых (ECM) — вероятностный алгоритм, эффективный для поиска небольших простых делителей больших чисел. Он использует ту же идею, что и метод p-1, но вместо мультипликативной группы целых по модулю p применяется группа точек на случайно выбранной эллиптической кривой над полем вычетов по модулю p. Если при вычислениях умножения точки получится ситуация, соответствующая вырожденности, это может привести к выявлению делителя через вычисление НОД.

Алгоритм выбирает кривую и точку P и пытается вычислить kP для некоторого большого k, составленного из малых простых степеней. При успешном совпадении по модулю простого делителя p наступает вырождение, выражающееся в том, что $kP \equiv O \pmod{p}$, и при вычислении определённых компонентов получается значение, дающее через $d = \gcd(Z,N)$ ненулевой делитель числа $N \in \mathbb{Z},\ N>1$.

ECM особенно хорош для чисел, у которых есть относительно небольшой простой делитель. По асимптотике временем его работы описывается субэкспоненциальной функцией вида $L_p\left[\tfrac{1}{2}, c\right]$, где параметры зависят от величины искомого делителя.

Сложность и практические рекомендации

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

Оценки сложности: пробное деление требует порядка $O(\sqrt{N})$ операций в худшем случае; Поллард Ро обычно работает за примерно $O(N^{1/4})$; методы типа квадратичного сита и GNFS имеют подэкспоненциальную сложность, выражаемую с помощью нотации L, например {FORMULA_21}. ECM для делителя p демонстрирует сложность порядка $L_p\left[\tfrac{1}{2}, c\right]$ относительно p.

На практике часто комбинируют методы: сначала выполняется быстрый набор тестов (пробное деление на малые простые, тесты на простоту), затем запускают Полларда Ро и p-1, затем ECM для удаления самых мелких делителей; если осталось большое ковровое число, применяют квадратичную решётку или GNFS.

Полезные советы и примеры для обучения

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

Для закрепления материала рекомендуется реализовать простые версии Полларда Ро и метода Ферма, прогнать их на наборе тестовых чисел и изучить поведение времени выполнения и вероятностей успеха при изменении параметров. Это даст интуицию о том, какой метод выбирать в реальных задачах факторизации.